Consider a scenario where we have to find the meaning of the word Zoology in an English dictionary. Where do we search it in the dictionary?
1. in the first half?
2. around the middle?
3. in the second half?
It is certainly more prudent to look for the word in the second half of the dictionary as the word starts with the alphabet ‘Z’. On the other hand, if we were to find the meaning of the word Biology, we would have searched in the first half of the dictionary.
We were able to decide where to search in the dictionary because we are aware of the fact that all words in an English dictionary are placed in alphabetical order. Taking advantage of this, we could avoid unnecessary comparison through each word beginning from the first word of the dictionary and moving towards the end till we found the desired word. However, if the words in the dictionary were not alphabetically arranged, we would have to do linear search to find the meaning of a word.
The binary search is a search technique that makes use of the ordering of elements in the list to quickly search a key. For numeric values, the elements in the list may be arranged either in ascending or descending order of their key values. For textual data, it may be arranged alphabetically starting from a to z or from z to a. In binary search, the key to be searched is compared with the element in the middle of a sorted list.
This could result in either of the three possibilities:
i) the element at the middle position itself matches the key or
ii) the element at the middle position is greater than the key or
iii) the element at the middle position is smaller than the key
If the element at the middle position matches the key, we declare the search successful and the searching process ends.
If the middle element is greater than the key it means that if the key is present in the list, it must surely be in the first half. We can thus straight away ignore the second half of the list and repeat the searching process only in the first half.
If the middle element is less than the key, it means if the key is present in the list, it must be in the second half. We can thus straight away ignore the first half of the list and repeat the searching process only in the second half. This splitting and reduction in list size continued till the key is either found or the remaining list consists of only one item. If that item is not the key, then the search is unsuccessful as the key is not in the list.
Thus, it is evident that unlike linear search of elements one-by-one, we can search more efficiently using binary search provided the list from which we want to search is arranged in some order. That is, the list needs to be sorted.
If the list to be searched contains an even number of elements, the mid value is calculated using the floor division (//) operator. If there are 10 elements in the list, then the middle position (mid) = 10//2 = 5. Therefore, the sixth element in the list is considered the middle element as we know that the first element in list has index value 0. If required, the list is further divided into two parts where the first half contains 5 elements and the second half contains 4 elements.
It is interesting to note that the intermediate comparisons which do not find the key still give us information about the part of the list where the key may be found! They reveal whether the key is before or after the current middle position in the list, and we use this information to narrow down or reduce our search area. Thus, each unsuccessful comparison reduces the number of elements remaining to be searched by half, hence the name binary search. Let us now discuss the algorithm of binary search.
Given a list numList of n elements and key value K, Algorithm shows steps for finding position of the key K in the numList using binary search algorithm.
Algorithm: Binary Search
Step 1: SET first = 0, last = n-1
Step 2: Calculate mid = (first+last)//2
Step 3: WHILE first <= last REPEAT Step 4
Step 4: IF numList[mid] = key
PRINT “Element found at position”,
IF numList[mid] > key, THEN last
ELSE first = mid + 1
Step 5: PRINT “Search unsuccessful”