Binary Search

11 min readSep 25, 2022

I recently reread my blog about searching algorithms, which you can find here, and was underwhelmed by the binary search section. The first blog was mostly focused on Breadth First Search(BFS) and Depth First Search(DFS). Today I wanted to give binary search its due. This time I’ll be including a lot more code snippets, and covering some relevant LeetCode questions.

Binary Search Background

First, a little background on binary search. Binary search is a type of search algorithm that can be used on sorted inputs such as sorted arrays, a series of numbers, or an alphabetized list. Binary search works by comparing the search target with the middle of the input. Every iteration either the middle is equal to the target, or half the list can be eliminated and the search can continue in the remaining half.

The worst case scenario is that the target is not found in the input. Since the input is cut in half each time, binary search runs in O(log n) time even in the worst case, which is still incredibly fast.

LeetCode 704: Binary Search

The first question, LeetCode 704, is a textbook example of binary search: sorted input, O(log n) runtime, return the position of the target. The first step of coding out binary search is to define the left and right ends of the search. We’re searching an input array so the first element is 0, and the last element is the length of the array-1.

Next, we iterate until we have searched through the whole input or found our target.

Each iteration we define m, the index in the middle of the left and right bounds of our search. If nums[m] is equal to the target, we’ve found our target at index m. Otherwise we eliminate half of the array, and iterate again. If we iterate, and iterate, and iterate until the ends of our search reach each other, then we know the target is not found in the array. The instructions for this question say to return -1 if the target isn’t found, so if the while loop finishes, we return -1.

In 11 quick lines there we have it, binary search.

Integer Overflow

One important note I would like to highlight is how m is calculated every iteration.

It is important that m is calculated this way as opposed to:

The second way of calculating m runs into a problem known as integer overflow. Computers have a maximum size integer that they can store. In JavaScript there is a command Number.MAX_VALUE that returns this number, which is 1.7976931348623157e+308. So if you were dealing with an enormous array and r + l > 1.7976931348623157e+308 you would have an integer overflow error.

This isn’t a problem with any LeetCode questions, they don’t test any arrays anywhere close to that size, but this is still a good tidbit to know. Java, no not JavaScript, had this method for calculating m built in for 9 years from 1997–2006 before someone managed to break it.

LeetCode 278: First Bad Version

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky -Donald Knuth

Despite the description for this question being completely different, this is still a binary search question, albeit with a twist. The first important difference is that we are making a call to an API, isBadVersion, that returns true or false instead of comparing to a target value. Additionally we’re looking for the first in a series and not a given value.

The first change is that we’ll be writing our solution inside of another function so that we have access to the ‘API’.

Our initial setup of the binary search is still mostly the same. We again start by defining the left and right bounds of our search, from zero to the nth version.

Again we iterate until the ends of our search reach each other, and define m in between the right and left bounds of the search. Three big differences in this version’s iteration step: there is no return within the iteration, we call isBadVersion instead of making a comparison, and there are only two conditions instead of three.

To break down the conditional statement, if isBadVersion is true the current version is bad and the first bad version is an earlier version. If isBadVersion is false we have a good version and the first bad version is a later version.

This is useful for moving the bounds of our search, but how do we know when we’ve found the first bad version, and how/what do we return? In the last question if we finished iterating the target was not in the input. In this case we must finish the while loop, but are guaranteed to have a first bad version in our input.

When we finish our iterating (line 19), we simply return r + 1.

Why though? Why would the solution be outside the bounds of our search? I think the best way to explain is to step through the function with a debugger. I’m a huge fan of the chrome debugger and snippets. If you want to try it yourself snippets are under the sources tab, and you can add a breakpoints by clicking on the number of the line you want your break point to be.

Here I’ve written the solution again in a chrome snippet and written the ‘API’ function set up like the first example given. In the first example we check 5 versions, with 4 being the first bad version.

The first few steps of the iteration are pretty simple so I’ve skipped ahead. The tan highlighted areas are the current values of the variables. I’ve paused just before the conditional on the highlighted line 6 is evaluated. r is 3, l is 3, and it isn’t shown but m is also currently equal to 3.

Take note that on line 4, our iteration continues while left is less than or equal to right. l === 3 === r so there is one more iteration before the while loop ends. isBadVersion(3) returns false, so we run our else statement and set l = m + 1. Now l equals 4 and r remains at 3. l is now greater than r so we stop iterating.

In this example, 4 is the first bad version, and we ended with l = 4 and r = 3. Three is the last good version, so r = 3 = the last good version. This holds true in other examples, at the end of iteration r is the last good version. If we know the last good version, the first bad version is the next one, and that’s why returning r + 1 is the correct solution. Returning m + 1 also works for the same reason, but m is defined inside the scope of the iteration. Alternatively you can return l, which always ends as the first bad version. I used r + 1 in the example to better highlight the behavior of the while loop on the last iteration.

LeetCode 34: Find First and Last Position of Element in Sorted Array

Alright, now we’re into medium level questions! This question is still fairly simple, and can be solved with only minor changes to our original binary search code. Here’s the two solutions side by side: original on the left.

There’s really only two locations where changes were made. The final return (line 10 and line 16) and what happens when the target is found(line 6). The only substantive change is within the conditional if (nums[m] === target).

In the original solution, we simply returned m. In this case we’re looking for a range of indices where nums[m] is equal to the target. So first we declare two variables to serve as the lowest and highest index of the target. Since the input is sorted, it is possible to find the first and last instance of the target element by incrementing or decrementing if the number before/after is the same. Then returning the lowest and highest index. There is a problem through, what is the time complexity of this block of code?

In the worst case scenario, where our input array is nothing but the target, this part of the code runs in O(n) time. By extension this whole solution unfortunately has a time complexity of O(n).

If only we had practice finding the first version of something. Wait, that sounds exactly like First Bad Version. Meaning we could do the exact same thing we did in that question to find the first instance of the target. Let’s try that approach instead.

Left: Updated current question, Right: First Bad Version

To find the first instance of the target the code is almost exactly the same as First Bad Version. Instead of calling the isBadVersion ‘API’, we check if nums[m] is greater than or equal to the target. At the end of this while loop, l will be the first instance of the target. That is assuming it is in the array. So the next steps are: check if the target is in the array, and then find the last instance of the target.

We can check if the target is in our array by comparing nums[l] to the target. If the target isn’t found, the instructions say to return [-1, -1]. We also save our current value of l in a variable start that will be returned later. Then to find the last instance of the target we set the search up again.

This is almost the exact same code as trying to find the first instance of the target. The sign of the inequality has been flipped, and the reassignments of r and l have switched places. Here’s the first while loop for comparison.

At the end of this iteration r will be equal to the index of the last instance of the target. Now with start and r we have the first and last index of the target so we have our solution.

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

I wanted to take a quick look at one last question. This is a question about binary search trees, which means you have to understand how to apply binary search to a tree. This is another medium question but the solution is actually fairly simple. The lowest common ancestor is a node whose value is between the two given node values. In a binary search tree, children smaller than the parent are on the left, children larger than the parent are on the right.

Here’s the complete solution. Starting at the root, if the current node is too small, go to the right child. If it is too big, go to the left child. If the current node value is in between p and q, simply return the current node.

This is all pretty simple for a medium difficulty question, but it is only simple if you have a good enough grasp on binary search and tree traversal.

Conclusion

If there’s anything I hope sticks with you, it’s this quote from Donald Knuth.