Programming Binary Search

Searching by trinstangage

Binary search is one of the basic algorithms in computer science. It can efficiently find an index of an element in a sorted list by repeatedly halving the search range until the element is found, so its running time is a logarithm of the list size. Many people were taught the algorithm or heard about it, but the clean way to implement it is not widely known as it seems. Why bother? Programming languages nowadays have some implementation of binary search in their standard library. For example, Kotlin provides a family of binarySearch functions for that purpose.

However, here is a twist. Kotlin follows Java collections tradition and these functions do not specify what index is returned when the element that is being searched for occurs multiple times. For example, run the following code that searches for the value of 7 in the list of integers 6, 7, 7, 7, 9, 9 (indexed from zero) and you'll see that the answer printed is 2, which is neither the first nor the last index of occurrence of this value in the list (they are 1 and 3 correspondingly):

But what if we need to find the index of the first occurrence of the specified value? More specifically, what if given a sorted list we need to find the lowest index i in the list such that list[i] >= value, returning list.size when all elements in the list do not exceed the specific value or when the list is empty. In fact, in Kotlin the following one-liner solves the problem, but it is not efficient, as it checks every element of the list in the worst case:

list.indexOfFirst { it >= value }.takeIf { it >= 0 } ?: list.size

Can you do it?

Can you write the code that solves this problem? Before reading further, please try it out. Here is a completely anonymous and blame-free way to test your binary search programming skills. Follow this link to Kotlin playground. There you’ll find a skeleton of searchLowerBound function that you need to implement and a comprehensive set of tests that verify correctness and efficiency of your implementation when you run the sketch.

Try to write an implementation so that it passes all the tests (PASSED ALL TESTS gets printed). It should not take a lot of time.

So, were you able to implement it? Did you write the simple code, the code that if obviously correct when you look at it? In fact, the correct solution takes just a single while loop and a single if statement without any need to handle corner cases of empty list, etc. It takes around 10 lines of code and does not take any mental energy to see that it works when you know the logic behind it. I'll explain it in this story.

As a bonus assignment you can scroll to the end of the main function in the playground and find there four more tests that are commented out behind BONUS TESTS line. Uncomment them. Does your code pass them, too? Can you pass them without increasing the complexity of your code? I'll show the trick to pass them at the very end of this story. Meanwhile, I'll appreciate if you share your results via an anonymous twitter poll at this link.

Generic binary search

It is easier to think about binary search when solving a more general problem than finding an element in a sorted list. It is quite a handy algorithm when you are trying to solve a problem that has the following properties. The answer to the problem is a number. You don’t know the answer, but given the answer you can code the algorithm to check if the number is an answer to the problem in a relatively straightforward way. So, essentially you have a predicate function ok(x) that returns true when x is a potential solution. Your task is to find the minimal x so that ok(x) returns true.

There is one crucial property that needs to be satisfied to apply a binary search algorithm. The predicate has to be monotonic. It means that if x is the lowest number making the predicate true, then it is also true for all the larger values of x. For example, the following table shows the values of a monophonic predicate over integers in range from 1 to 6:

   x   :   1  2  3  4  5  6
ok(x)  :   F  F  T  T  T  T

In binary search algorithm we introduce two variables. One variable keeps the index of the left side of the currently searched range and is commonly shortened to l (however, make sure your programming environment uses a font that makes it look distinct from the number 1), while the second one keep index of the right side (r). The algorithm maintains the following invariant throughout its operation:

• ok(l) is false
• ok(r) is true

Binary search is a primitive example of a divide and conquer algorithm. It repeatedly halves the range from l to r while maintaining this invariant until l and r only differ by one, thus exactly pinpointing the indices at which monotonic predicate turns from false to true:

   x  :  1  2  3  4  5  6
ok(x) :  F  F  T  T  T  T
            ^  ^
            l  r  // at the end

So the whole solution is to run the following loop:

while (r - l > 1) { 
    val m = (l + r) / 2  // compute the midpoint of l..r interval
    if (ok(m)) 
        r = m  // Maintain invariant: ok(r) is true
    else 
        l = m  // Maintain invariant: ok(l) is false    
}

If you keep the loop invariant in mind when writing this code it is easy to see what exactly needs to be put into each of the branches of the if statement. No chance for any kind of off-by-one errors.

But we need to initialize the values of l and r before that start of the algorithm so that the invariant holds. How do we find such an initial l that ok(l) is false? In general, we cannot set l to the left of our search range (index 1 in the above picture), because the predicate might already be true there. The same problem is with r. Now, in some specific problems we might happen to know initial values of l and r that maintain the invariant, but when it is not case we can use the approach called a sentinel value. We set the initial l to the number before the beginning of the search range and just pretend ok(l) is false there and set r to the number after the end of the search range and just pretend ok(r) is true.

   x  :  0  1  2  3  4  5  6  7
ok(x) : [F] F  F  T  T  T  T [T] // [x] are virtual values
         ^                    ^
         l                    r  // at the beginning

We don’t need our predicate function to return those virtual true and false values. The binary search algorithm only ever evaluates predicate ok(m) for values of m strictly between the current values of l and r. The initial values work as sentinels that ensure that predicate is only evaluated in the search range.

Array search

The original problem of searching an element in a sorted list is just a specific instance of a binary search when predicate ok(i) is list[i] >= value. Valid indices in the list run from 0 to list.size - 1, so using the approach of sentinel values we start with l = -1 and r = list.size. We are asked to return the first i where the predicate is true, so we consult our invariant and see that at the end we need to return r as the answer. Here is the simple code that implements searchLowerBound function and passes all the main tests:

Integer overflow

Unfortunately, this code will not pass the bonus tests. The size of the list in those tests is equal Int.MAX_VALUE and integer overflow problems in two places in this code prevent it from working correctly.

The first one is r - l > 1 check. At the very start, when l = -1 and r = Int.MAX_VALUE the result of r - l overflows integer range, becomes negative, makes the loop condition false, causes immediate exit from the loop, and produce a wrong answer. A better way to write this check is l + 1 < r. It is always correct and overflow-free even when you solve a general binary search problem on the full range of integers from l = Int.MIN_VALUE to r = Int.MAX_VALUE, since l is always less that r and thus l + 1 never overflows.

The other problem is in the code that computes the middle as (l + r) / 2. This sum might overflow when l and r are close to the end of the integer range. We cannot use unsigned arithmetics here, since we start with l at a negative value. We could use Long type, but what if we had to solve the similar problem with Long indices? The right way to fix it in this particular case is to write (l + r) ushr 1, using an unsigned shift to the right instead of division by two, relying on the fact that here the values of m are never negative and overflow in addition never goes beyond the highest bit. This expression yields the correct value for this particular range of values of l and r that this binary search algorithm can produce.

Side note: However, it is not a generic solution to compute a mid-range for the full range of integers. You'd either need to use higher-precision integers or more complicated bit-fiddling tricks. I'd highly recommend reading Hacker's Delight for those who are interested to learn more about those (see item 2–5 for this particular problem).

All in all, the following code successfully passes all the tests for the original array search problem, including the bonus ones for the maximal list size:

Conclusion

Binary search seems like an easy problem, but is tricky to code right in practice. Being able to write algorithms like this one is an essence of competitive programming that I’ve previously covered in the “Programming as a Sport”. But learning them is also known to boost your chances at a technical interview and teaches you important principles of algorithm design that you can apply anywhere.