Binary search is one of the most useful searching algorithms out there. It’s main use is to find the position of a target value within an array. Note: the array must be sorted for binary search to work.
How Does Binary Search Work?
A common explanation for this algorithm would be:
- Compare target value to middle element of array.
- If they are not equal, we can eliminate one half of the array, since all values to the right of the middle are greater than it and all values to the left are smaller than it. This means that if the middle value is greater than the target value, we can eliminate the right half of the array since all those values will be greater also.
- We repeat this process until we have found the target value.
- If at anytime the remaining half is empty, then the target is not in the array.
Implementation
The code below is a Python implementation of binary search:
Visualization
Now, here’s a quick visualization of the search algorithm courtesy of https://www.cs.usfca.edu/.
You can see how we begin with the middle element of the array and, seeing that it is smaller than the target, compeltely eliminate the left half of the array. Then we find the middle element of the remaining array and do the same thing again. The process repeats until the target is reached or the remaining array is empty.
Time Complexity of Binary Search
The time complexity of this algorithm is O(n). In the best case, time complexity would be O(1), where the central element of the array is the target we’re looking for.
Space Complexity of Binary Search
The space complexity of this algorithm is O(1). This is because no matter how big the data we’re working with, we always keep track of the same number of variables.
