Generalising Binary Search

Alaap Surendran
Mar 24 · 6 min read

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.

Illustration of binary search for key = 71

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:
return mid
else if A[mid] < key:
L = mid + 1
else
R = mid - 1
return -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
my_sqrt(x):
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
else
R = mid
return L + (R - L)/2

This idea by itself shows us how powerful binary search is.

Striping the implementation details

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.

The boundary in our search sorted array 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?

Looks like we are stuck :c

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.

Did you get it? :p

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 ;)

Conclusion

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:

Connect • Learn • Grow

DSCJSSSTU

DSC JSSSTU is a non-profit community committed to helping developers to develop, learn & share.

DSCJSSSTU

Developer Student Clubs JSSSTU, powered by Google Developers, is a non-profit student community that aims to inspire intelligent minds in the field of technology. DSC provides opportunities where developers, designers and managers work together to carry out real-time projects.

Alaap Surendran

Written by

DSCJSSSTU

Developer Student Clubs JSSSTU, powered by Google Developers, is a non-profit student community that aims to inspire intelligent minds in the field of technology. DSC provides opportunities where developers, designers and managers work together to carry out real-time projects.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store