Types of Binary Search

(There’s more than the two)

Audience

This article is aimed at developers looking to understand a little bit more about binary search. It requires a passing knowledge of Java. Having a small amount of previous experience with binary search is advantageous, but not essential.

Argument

Let’s start off with a bit of motivation. Say we have a sorted list of numbers, and we would like to find where in this list a particular number appears.

An efficient way of doing so would be to look in the middle of the list, and see if our target is greater or smaller than this number. If it is greater we look on the right hand side of the list (as we know all numbers after the middle are greater than it), if it is not we do the opposite.

Let’s take an example.

[1, 2, 3, 4, 5, 6]

Imagine we are looking for the number 3. First of all we find the middle of the list. The length of our list is 6, the middle index is 3. The number at index 3 is 4. Our target is less than that, so we look to the left of the middle. This brings the list down to:

[1, 2, 3]

The middle number is now 2, we need to go higher! At this point we only have one item left in the list (3), we have found our solution.

Let’s look at how we might code that up.

So far, so good! Although this might seem a fairly niche problem, there are a number of places we can use this technique. Let’s take an example from LeetCode.

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

We can use binary search to solve this! If you think of our search space as being between 0 and x, we look in the middle of these two numbers, square this and check if it is greater than or lower than x. If it is greater our square root must be on the left of the middle, if not then it must be on the right!

OK, so that’s one type of binary search. But what are the other types? Let’s take another problem from LeetCode.

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

So how do we find a peak? Let’s draw some diagrams.

Different types of peak

The first two are edge cases. They represent when the peak is the last or first element in the list. The final image represents what most people were likely thinking of.

We can centre in on a value by moving to the left if the value to the right of our current one is decreasing, and the right if it is increasing. Think about it like a hill. If the value on our right is decreasing we’re on the way down a hill, so a peak is behind us, and vice versa.

I’ll admit it’s not the clearest sentence, re-read it a couple of times and go ahead to the example for clarity.

We now introduce our second type of binary search, where we need to examine not only an element, but the one immediately to the right.

Let’s take an example where the peak is exactly in the middle, the array [1, 3, 5, 3, 1]

Below we have a colour coded example of how our new algorithm would operate on the array. The left, middle and right pointers are signified by L , M and R. We are using blue to represent the ends of our list space, green to be the middle, and yellow to be the value to the right.

An intuitive way to think about this is that we are doing binary search, but instead of looking at single values, we use a window of two. By changing the boundaries we can keep the green and yellow squares within the blue ones.

Our termination conditions are also slightly different. Once our while loop has exited, we have one last pair of numbers to check. As we know a peak exists in the array, it is safe to say that our current index is where the peak resides. However, in a more general implementation, we would need to do a final check!

Our final binary search has to do with needing to check the numbers to the left and right of our current place. This time we no longer need to maintain a window of two, but instead a window of three.

That’s it! That’s our three different binary search implementations:

1. Basic binary search, examining only the element we are interested in.
2. Right looking binary search, examining an element and its right neighbour.
3. Left and right looking binary search, examining an element and its left and right neighbours.

Conclusion

This short article has covered binary search, the motivation behind it, as well as three different approaches to solving search problems!