Binary Search: Searching Made Easy
Updated: Jun 3, 2022
Algorithm
Binary search is one of the most commonly used search algorithms. It is also one of the fastest searching algorithms in terms of time complexity. Binary search works only sorted arrays. The algorithm divides the given array into two halves and does its searching on these halves based on certain conditions. Hence the name binary search (since it splits the array into two halves).
Binary search works by reducing the search space by half each time, in each iteration half of the elements are eliminated from the current search space. Binary search starts searching from the middle of the array and moves outwards (either left or right), unlike some other search algorithms like linear search that begin their search from the first element of the array.
For a given input array arr and a target element lets say x, binary search does the following steps:
To begin with the algorithm considers the entire array as its search space. We create two variables left and right representing the index of the first and last elements in the search space.
Next we need to find the middle element by dividing the search space into two halves. If our search space has n elements, we can find the middle element by using the formula: mid = (left+right)/2. Now our search space is divided into halves, one half on the left of middle element and the other half on the right of the middle element.
Now compare the target element x to the middle element arr[mid] obtained from the previous step. There are three possibilities here: 1. x is equal to middle element 2. x is greater than middle element 3. x is less than middle element.
If x is equal to middle element we have found our answer, so we return the index of the middle element as our result.
If x is greater than middle element, we can discard all the elements on the left of middle element. We can safely do this because we know that the input array given to us is sorted, so if x is greater than middle element it should obviously be greater than all elements before the middle element. So, definitely you cannot find x by searching in the left half of the array. Hence we discard all the elements in the left half. Therefore our new search space now is the right half (all the elements on the right of middle element), so we update left = mid+1 and right remains the same. Thus our new search space is from index mid+1 to index right.
Similarly if x is less than middle element, we know there is no benefit searching the right half elements, since x will obviously be less than all elements on the right of middle element. Therefore update right= mid-1 and left remains the same. Thus our new search space is from index left to index mid-1 (left half).
We repeat steps 2-6 until we find the middle element or the search spaces reduces to 0 elements (target element not present in the array). If the given target element is not found we return -1.
Note: Our above formula to calculate middle element, mid = (left+right)/2, can result in overflow for large arrays. We can alternately use the below for to calculate middle element to prevent overflow condition,
mid = left + (right-left)/2
How mid=left + (right-left)/2 prevents overflow?
Please refer the detailed explanation here.
Working
Consider we are given the array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] and the target element is x = 19 as shown below:
Initially our search space is the entire array as highlighted in grey. We create two variables left and right representing the indexes of the first and last elements in the search space, as shown in the below diagram. Initially left = 0 and right = 9. So, mid = (0 + 9)/2 = 4.5 ~ 4.
Now we compare x to middle element 9. Clearly 19>9, so we discard all the elements on the left of mid (Discarded elements are shown using X mark). Also now our new search space is all the elements on the right of middle element (highlighted in grey). So we update left = mid+1 = 5 and right remains same.
Again we calculate middle element using our new left and right values. mid = (5+9)/2 = 7.
We repeat the step of comparing x to the middle element. Again x is greater than middle element (19 > 15). So we shift our search space to the right half by updating left = mid + 1 = 7+1 = 8 and right remains same. Thus our new search space now is from index 8 to 9 as highlighted in grey in the below diagram.
Now mid = (8 + 9)/2 = 8.5 ~ 8. Same is shown in diagram below:
Again 19 > 17, so left = mid + 1 = 8 + 1 = 9 and right remains same.
Now the target element x is equal to the middle element, i.e. arr[9] = x = 19, therefore we have found the target element we are searching for, so return 9 as our result indicating that the target element is found at 9th index in the given input array.
Implementation
We can implement binary search using both iterative as well as recursive approaches. Below code shows both these implementations:
Iterative Approach
Language: Go
Recursive Approach
Language: Go
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Complexity Analysis
Time Complexity: O(log n)
In the worst case our algorithm would end up doing log n comparisons to find the target element . The worst case occurs when the target element is the first or last element in the input array or the target element itself is not present in the array.
How time complexity is O(log n)?
Consider you are given an array with 8 elements arr={2, 4, 6, 8, 10, 12, 14, 16} and your target element is 2. As we know binary search discards half the elements in each comparison. In the first comparison the search space reduces to 4 elements, in the second comparison it reduces to 2 and then 1. So in total we had to make 3 comparisons. Similarly if the array had 16 elements, it would take 4 comparisons, i.e. 16 - >8 - >4 -> 2 ->1 in the worst case. Now if you observe both the cases where n=8 and n=16, the number of comparisons we had to do corresponds to a logarithmic function with base 2. For n=8, log2 8 = 3 and for n=16 it is log2 16 = 4 which correlates to 3 and 4 comparisons that our algorithm had to do respectively. And this relation is true for all values of n and hence the time complexity is O(log n).
Space Complexity: O(1)
No extra space is used is used for iterative approach. For recursive approach space complexity is O(log n) if you consider the recursion call stack otherwise O(1).
Output
We can test our algorithm with the below code snippet:
We get the below output after executing the test:
Note: Position displayed in the above output is array index based.
Advantages
Binary search eliminates half the elements in each iteration, thus has a time complexity of O(log n), therefore it is more efficient as compared to other search algorithms like linear search.
Binary search is preferred over other search algorithms especially when the size of the input array is large.
Disadvantages
Binary search cannot be efficiently implemented for linked lists as linked list does not allow random access in O(1) time as compared to arrays. Remember quick access to elements is needed to reach the middle element efficiently in binary search.
Binary search only works on sorted arrays.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section.
Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
