Binary search is an awfully underrated algorithm. The way it’s usually introduced in a classroom is to show how it can be used to find an element in a sorted array. Although this exercise shows the general gist behind binary search, it hides the truly beautiful idea behind the algorithm. In this article, I wish to attempt to explain it so that you can know when you could use a binary search, even in the most unusual situations.
So, uh, what is binary search?
Just so we are all on the same page, here’s a quick refresher on binary search. Consider an array of sorted elements.
Say, we are searching for the element 71. One way to achieve this would be to search from left to right, one by one. But now, we know that the array is sorted, we can use it to our advantage. We set two pointers, one pointing to the lower element in the search space, and the other pointing to the highest element in the search space. Each iteration, we cut the search space into half by finding the middle element of the search space. If the middle element is the key, then we return the middle as the position of our key. If the key (ie, 71) is greater than the middle element, we search to the right of the middle element, otherwise, we search to the left of the middle element.
It is also possible that we never find the element in the range. Here is an illustration for key = 32
# Pseudocode for binary search
binarySearch(A, N, key):
L = 0, R = N-1
while L <= R:
mid = L + (R-L)/2
if A[mid] == key:
else if A[mid] < key:
L = mid + 1
R = mid - 1
Continuous Search Space
One of the common misconceptions about binary search is that the search space has to be discrete, like a sorted array of distinct objects. Let’s try applying the binary search on a continuous search space.
The problem is to find the square root of a number to some precision. Then we can for sure say that the square root of x lies between the continuous range [0, x]. Now we use the same principles of binary search. Here, our key is x, and we are trying to find a value t in [0, x] such that t*t == x. Since the square root is a monotonically increasing function, we can use binary search as follows:
# Pseudocode for sqrt function using binary search
epsilon = 0.001 # the precision to which
# we want to calculate the
# square root.
L = 0, R = x
while (R - L > epsilon):
mid = L + (R - L)/2
if (mid*mid <= x):
L = mid
R = mid
return L + (R - L)/2
This idea by itself shows us how powerful binary search is.
Striping the implementation details
In its purest form, binary search’s essence boils down to finding a monotonic function. This could be a mathematical function, or in most cases, a condition.
Let’s understand what I mean by that using the above example of finding the square root of a number. Consider the graph of y = x² and y = 2, where we are trying to find the square root of 2.
Because of the monotonically increasing nature of y=x², we find that we can divide the interval [0, 2] into two halves. One where x² is less than 2, and the other where x² is greater than 2. Finding this boundary is what binary search actually does!
In this case, if mid is in the green region, then we search to the right and if mid is in the red region, then we search to the left for a better answer.
In fact, this idea extends to any binary search problem.
So, let’s try this technique out on a classical problem :^)
Finding the smallest element in a rotated array that was initially sorted
This is one of the many cases were knowing this interpretation of binary search comes in handy! There is no sorted array here, yet we can still apply binary search to get O(log n) solution! The problem statement is as follows. Consider a sorted array. Now someone rotated it (shifted it to the left or right wrapping the elements around) by some amount. We are to find the smallest element of this array. For example, consider this array, were 15 is the smallest element:
Say we found mid, could we find out if the smallest element is to the left or to the right of mid?
Let’s take a step back. How should our monotonic condition look? Where should it draw the boundary?
Now I ask you take a step back and see if you can observe a condition that generates this boundary.
Yep! If you guessed “comparing with the last element”, then congrats!!! Pat yourself on the back, because it isn’t that obvious at all at the first glance! Now we can perform the binary search as usual to find the smallest element 15.
Note: you could also compare all the elements with the first element ;)
We have barely looked at the applications of binary search. The main take away I want you, dear reader, to take away from this article is
1. The search space need not be an array or be discrete. It could be anything, including all-natural numbers, all of the real numbers, etc.
2. If you can find the monotonic function/condition in your problem, then binary search is your best friend
Hopefully, this article gave you some new insight into one of my favourite algorithms. Till the next time, Happy coding!
Further Reading and Problems:
- CSES problem set on sorting and searching: https://cses.fi/problemset/
- Aggressive cows (problem): https://www.spoj.com/problems/AGGRCOW/
- Errichto’s binary search tutorial: https://www.youtube.com/watch?v=GU7DpgHINWQ
- Antti Laaksonen’s Competitive Programmer’s Handbook (Chapter 3, last section): https://cses.fi/book/book.pdf
- Codeforces problem set with binary search tag (Need not always need bin search): https://codeforces.com/problemset?tags=binary%20search