Updated: Jun 3, 2022
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