Three Things to Know about Binary Search

Conceptually, binary search is a very easy to understand algorithm. However, implementing it is very difficult, especially when you try to implement many variants of it. My goal is to get you understand different ways to implement binary search so well, this will be the last guide on binary search that you will ever need.

A few points: First, this article is a long read. Sometimes, when we explain things, we tend to skip over things might not be obvious to everybody. Second, I use Python for the code. In Python, the first element in an array has index 0 and the last element in an array has index len(array)-1. After reading this guide you will be able to adapt it to 1-index languages. Also, Python is a dynamic-typed language. If you use static languages like C++, use the proper data types for lo and hi.

Gratitude: I learned the concept of intervals and exit condition from labuladong binary search tutorial. It is the best public guide on Algorithms for interview I’ve read. Some things you read here are expansions of ideas from him. I think his explanation of finding left and right boundaries is too fast, so I devote a decent chunk of this guide to that.

Conceptual review

Binary Search is a divide and conquer algorithm. The goal is to find a target value in a sorted array. It can only works on data that is sorted, usually in increasing order. The algorithm works by selecting a middle point in an array, then divides the array into three parts: the part that is less than the middle, the middle, and the part that is greater than the middle. See figure 1 for an explanation.

Why people struggle with binary search?

From personal experiences and from reading StackOverflow, it seems that the majority of problems in implementing binary search comes from:

• Out-of-bounds -> Bad interval consideration
• Target exists but not found -> Gaps between intervals
• Wrong elements returned -> Not considering the exit conditions
• Edge cases at the first or last elements
• Integer overflow (found in static typed languages like C++)

If you need to be proficient at implementing binary search, you need to understand why all of these happen. There are three steps to understanding: (1) interval, (2) partition, and (3) exit condition.

One: Intervals

First, let’s review the concept of intervals. Close intervals include the end value, and open intervals do not.

• The interval [1,5]has the following elements: 1 2 3 4 5
• The interval [1,5)has the following elements: 1 2 3 4
• The interval (1,5)has the following elements: 2 3 4

Consider the following function that prints a set of integers.

The exit condition of the loop is lo > hi. When we increment lo until lo = hi+1, it exits. This means that the function will prints out all values in the close interval [lo, hi] with both lo and hi included.

Now, consider the following function.

The exit condition of this function is that lo >= hi. When we increment lo until the point where lo == hi, it exits. This means that the function will not print hi. This function prints out all values in the left-opened interval [lo, hi)

Takeaway 1. If we want a both-end-closed interval [lo, hi], then we use lo <= hi as our loop condition. On the other hand, if we want a left-end-open interval [lo, hi), we have to use lo < hi in our loop condition.

Now, let’s apply this to traversing a list. In our closed interval, we want to traverse all elements in the range [0, length(array) - 1], so our traversal loop will be as follows:

And if we want to traverse a left-opened interval, then the last element (not included) should be length(array), and our interval would be [lo, length(array))

My recommendation is that you use the closed interval [lo, hi] from here on whenever you implement binary search in the future. Not only are closed interval easier to understand, but it also has symmetric property that open interval doesn’t have. This is illustrated by the following functions that traverse the intervals backward by decrementing hi. Symmetry makes the reversed version of closed-interval possible, but not the open-ended interval version. The first function covers [lo, hi], but the second function covers (lo, hi] and not [lo, hi).

Two: Partitions

If the list has more than one element, we can partition it into three sub-lists. [lo, middle - 1] is the left sub-list, [middle, middle] is a one-element list, and [middle + 1, hi] is the right sub-list.

Takeaway 2. The three intervals [lo, middle - 1] [middle, middle] and [middle + 1, hi] are non-overlapping, and they cover the entire closed interval [lo, hi]. This makes sure that all elements in the list are taken care of.

The choice of interval is where a lot of people trip up:

• Why does the left interval ends at middle-1? Because remember that these are closed (inclusive) intervals. [lo, middle-1] means that this interval also have element middle-1. If we use interval [lo, middle] then our interval will overlap with the [middle, middle] element, which we don’t want. Same logic for [middle+1, hi].

I implemented using the three closed intervals that I have selected.

At the end, we exit the while loop because lo > hi, this signifies that we cannot find target inside array. It returns None.

Takeaway 3. Use mid = lo + (hi - lo)//2. When you implement binary search in other languages, use this instead of mid = (hi+lo)//2. This is because hi+lo can overflow (Skiena’s book was where I first learned about this).

What if instead of searching on the closed interval [lo, hi], we want to search on the interval [lo, hi)? We can still partition the array, but all of our partitions (except the middle one) has to have open right interval. This is because we have adapted the binary search to right-opened interval, so what it receives should be right-opened. Recall that our starting condition should be [0, length(array)) because length(array) is not included in the interval.

The partitions we wants are [lo, mid) [mid, mid] and [mid+1, hi).

• Why does the left interval ends at mid? Because this interval is [lo, mid) so it doesn’t include the mid element. Therefore it doesn’t overlap the [mid, mid] interval. Confirm by yourself that they do not overlap, and still cover the entire right-open interval [lo, hi).

  Three: Exit conditions

In our closed interval example, if target is not in array, then eventually lo > hi and the while loop exits. But where are lo and hi pointers in these cases?

Consider the following sorted array [0 1 2 3 4 5] and three cases of target:

• Target = -2
• Target = 10
• Target = 3.5

Here’s where the lo and hi pointers will be once we exit the loop (Note that lo > hi in all of these cases).

Takeaway 4. If target doesn’t exist in array, then lo shows the index where target would be if we insert it into array. The explanation of this is fairly straightforward:

• In the first case, we only update the value of hi, because nums[mid] > target at every iteration of the while loop. This means that lo stays at 0 until we exits. Because the new element is smaller than every other element, we insert it at location 0.
• In the second case, we only update the value of lo, because nums[mid] < target at every iteration of the while loop. The loop exists when lo > hi, or lo == hi + 1. Because hi pointer doesn’t change value, we exit the loop when lo == length(array). Because the new element is larger than every other element, we insert it at location length(array). (array refers to the original array)
• In the third case, since target doesn’t exist, we partition the list into two parts: those that are smaller than target, and those that are larger than target. When the loop exit, lo marks the beginning of the second parts. When we insert target element, it will take the index where lo is pointing to.

This can be hard to get if you are unfamiliar, so go through several examples yourself step by step. Debugging tools can help you look at the value of lo and hi at different iterations of the loop. Another way to think about this is that lo pointer index shows how many elements are strictly smaller than target. In the first example, there is 0 element that are smaller than -2. In the second example, there are 6 elements that are smaller than 10. In the third example, there are 4 elements that are smaller than 3.5.

Why are we doing all these? Because I want to show you how to modify binary search algorithm for many other tasks, with each task built upon the previous one. Trust me, it will be all worth it.

Variants of the binary search

Task 1. Find the number of elements smaller than target

Our previous observation is an excellent starting point. When we exit the loop, we returns lo instead of None. However, what should we do when we find target in the array? We know that, if target doesn’t exist in array, then the function will exit with lo points to the solution. In other word, if array[mid] == target is not called, then the function will exit with lo points to the solution. We can modify our previous function such that when array[mid] == target, instead of returning mid, we update either the lo or the hi pointer.

So, which pointer do we update? It depends on where we want to search. If we found a value that is equal to target and we want to know how many elements are smaller, it makes sense to search exclusively in the lower partition. Therefore, we want to update the hi pointer to shrink our search intervals into [lo, mid-1].

This is our solution. Notice line 8 is where we make the modification.

Task 2. Find the first appearance of target

Imagine if our sorted list do not have unique elements. We are tasked with finding the first appearance of target. We cannot use regular binary search, because it is not guaranteed that we will return the correct index.

This task is very similar to task 1 (It’s up to you to see the reason why). In fact, the solution for task 1 will work most of the cases. The only problem comes when we have elements at the edge of the array or when target is not in array. Remember that the solution for task 1 return number of elements in the array that are smaller than target, so the result can range anywhere from 0 to length(array).

• If the while loop exists when lo == len(array), then we know that all elements are smaller than target. We can return -1 because target doesn’t exist

• Otherwise, lo points to the first element that is greater than or equal to target (read this carefully). This element could be lo or it could be greater than lo. We simply check if array[lo] == target.

  Task 3. Find the last appearance of target

Can we do the reversed? Yes, we can thanks to the symmetry of the closed interval (another reason why I recommend closed interval when Coding binary search). We need to modify the following:

• When array[mid] == target, we update the lo pointer now, so that we can focus on the closed interval [mid+1, hi]

• We return the value of hi. This value ranges from -1 to length(array)-1 (go back to Figure 2 to see the ranges of hi). If hi == -1, then all elements are greater than target, so we return None

  Task 4. First defective element

Given two arrays, one full of defective elements (denoted as "F") and one full of normal elements (denoted as "T"). It is not known if both arrays are non-empty. We join the two arrays together so that the resulting array looks like this:

[T T T T T T F F F F F F F F F F F]

Our task is to find the number of normal elements. To see how binary search can help, consider an array of only two unique numbers, 1 and 2:

[1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2]

It is immediately obvious that we can use the function elements_less_than to find the number of 1s in the array. Now, imagine that all of our inputs consists of the numbers 1 and 2 arranged in this fashion. We can modify the function by eliminating unnecessary code:

Notice two changes:

• We remove array[mid] > target branch condition. The reason why we don’t need it is because the array only has 1 and 2, so we don’t have any elements greater than 2.
• We change the array[mid] < target into array[mid] == 1. This is because the only way an element is less than 2 is that it is equal to 1.

Simply replace 1 and 2 with T and F to get our solution. Another way to think about this is that when we find T, we need to update the search toward the upper partition and vice versa.

Takeaways

1. This is my recommended binary search framework. It uses closed interval [0, length(array) - 1]. Remember the three partitions [lo, mid-1], [mid, mid], and [mid+1, hi]. If you want to use open interval [0, length(array)), just remember to partition correctly.
2. You can now debug any binary search code by considering the following four things:

• What is the interval?
• Do the partitions overlap and cover the entire array?
• Where will the location of lo and hi be when the loop exits?
• What happen if target is located at the edges?

Happy coding!

Here’s are some problems for training:

Find Smallest Letter Greater Than Target – LeetCode

Sqrt(x) – LeetCode

Find Minimum in Rotated Sorted Array – LeetCode