Binary search algorithm
Definition
Search a sorted array by repeatedly dividing the search interval in half.
Begin with an interval covering the whole array. If the value of the search
key is less than the item in the middle of the interval, narrow the interval to
the lower half. Otherwise narrow it to the upper half. Repeatedly check
until the value is found or the interval is empty.
Generally, to find a value in unsorted array, we should look through
elements of an array one by one, until searched value is found. In case of
searched value is absent from array, we go through all elements. In
average, complexity of such an algorithm is proportional to the length of
the array.
Divide in half
A fast way to search a sorted array is to use a binary search. The idea is to
look at the element in the middle. If the key is equal to that, the search is
finished. If the key is less than the middle element, do a binary search on
the first half. If it's greater, do a binary search of the second half.
Performance
The advantage of a binary search over a linear search is astounding for
large numbers. For an array of a million elements, binary search, O(log N),
will find the target element with a worst case of only 20 comparisons.
Linear search, O(N), on average will take 500,000 comparisons to find the
element.
Algorithm
Algorithm is quite simple. It can be done either recursively or iteratively:
1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
o searched value is less, than the middle element. In this case, go to
the step 1 for the part of the array, before middle element.
o searched value is greater, than the middle element. In this case, go
to the step 1 for the part of the array, after middle element.
, Now, we should define when iterations should stop?
First case is when searched element is found.
Second one is when subarray has no elements.
In this case,
We can conclude, that searched value doesn't present in the array.
Illustration of Binary search
• X[12]:
• Search for b=12
• mid = (0+11)/2 = 5. Compare b with X[5]: 12<20.
• So search in left half X[0..4]
• mid = (0+4)/2 = 2. Compare b with X[2]: 12 > 7.
• So search right half X[3..4]
mid = (3+4)/2 = 3.Compare b with X[3]: b=X[3]=12.
Return 3.
Definition
Search a sorted array by repeatedly dividing the search interval in half.
Begin with an interval covering the whole array. If the value of the search
key is less than the item in the middle of the interval, narrow the interval to
the lower half. Otherwise narrow it to the upper half. Repeatedly check
until the value is found or the interval is empty.
Generally, to find a value in unsorted array, we should look through
elements of an array one by one, until searched value is found. In case of
searched value is absent from array, we go through all elements. In
average, complexity of such an algorithm is proportional to the length of
the array.
Divide in half
A fast way to search a sorted array is to use a binary search. The idea is to
look at the element in the middle. If the key is equal to that, the search is
finished. If the key is less than the middle element, do a binary search on
the first half. If it's greater, do a binary search of the second half.
Performance
The advantage of a binary search over a linear search is astounding for
large numbers. For an array of a million elements, binary search, O(log N),
will find the target element with a worst case of only 20 comparisons.
Linear search, O(N), on average will take 500,000 comparisons to find the
element.
Algorithm
Algorithm is quite simple. It can be done either recursively or iteratively:
1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
o searched value is less, than the middle element. In this case, go to
the step 1 for the part of the array, before middle element.
o searched value is greater, than the middle element. In this case, go
to the step 1 for the part of the array, after middle element.
, Now, we should define when iterations should stop?
First case is when searched element is found.
Second one is when subarray has no elements.
In this case,
We can conclude, that searched value doesn't present in the array.
Illustration of Binary search
• X[12]:
• Search for b=12
• mid = (0+11)/2 = 5. Compare b with X[5]: 12<20.
• So search in left half X[0..4]
• mid = (0+4)/2 = 2. Compare b with X[2]: 12 > 7.
• So search right half X[3..4]
mid = (3+4)/2 = 3.Compare b with X[3]: b=X[3]=12.
Return 3.
