Binary Search
(Divide and Conquer Search)
[Sequential search is simple and easy method. It is efficient for small list of elements but highly inefficient for larger lists. In the worst case we have to make “N” comparisons to search the element]
In binary search a particular item/element with a certain key value say “num” is to be searched. Approximately middle entry of the array is located then it is compared with “num”. if value matches then the search becomes successful otherwise if middle element is greater then “num” it means the element “num” may be present in first half otherwise it may be present in second half.
After deciding the half, we will repeat the process till either the element is found or the interval becomes empty.
This method is called binary search because at each step we reduce the length of the array to search by half.(2 parts).
We can imagine the efficiency of the binary search by the fact that in just about 20 steps this method can locate an element in a total of 1 million elements.
Note: elements should be sorted (Ascending order)
Binary Search Advantages
The advantages of binary search algorithm are-
• It eliminates half of the list from further searching by using the result of each comparison.
• It indicates whether the element being searched is before or after the current position in the list.
• This information is used to narrow the search.
• For large lists of data, it works significantly better than linear search.
Binary Search Disadvantages
The disadvantages of binary search algorithm are-
• It employs recursive approach which requires more stack space.
• Programming binary search algorithm is error prone and difficult.
• The interaction of binary search with memory hierarchy i.e. caching is poor.
(because of its random access nature)
Binary Search Example-
Consider-
• We are given the following sorted linear array.
• Element 15 has to be searched in it using Binary Search Algorithm.
| a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] |
| 3 | 10 | 15 | 20 | 35 | 40 | 60 |
Binary Search Algorithm works in the following steps-
Step-01:
• To begin with, we take beg=0 and end=6.
• We compute location of the middle element as-
mid = (beg + end) / 2
mod = (0 + 6) / 2
mid = 3
• Here, a[mid] = a[3] = 20 ≠ 15 and beg < end.
• So, we start next iteration.
Step-02:
• Since a[mid] = 20 > 15, so we take end = mid – 1 = 3 – 1 = 2 whereas beg remains unchanged.
• We compute location of the middle element as-
mid = (beg + end) / 2
mid = (0 + 2) / 2
mid = 1
• Here, a[mid] = a[1] = 10 ≠ 15 and beg < end.
• So, we start next iteration.
Step-03:
• Since a[mid] = 10 < 15, so we take beg = mid + 1 = 1 + 1 = 2 whereas end remains unchanged.
• We compute location of the middle element as-
mid = (beg + end) / 2
mid = (2 + 2) / 2
mid = 2
• Here, a[mid] = a[2] = 15 which matches to the element being searched.
• So, our search terminates in success and index 2 is returned.
