Get binary search right the first time

Binary search is one of the first algorithms that people learn. The idea is wonderfully simple: Yet it’s so easy to get the details wrong. In fact, nearly all binary searches are broken.

If you set out to write a binary search, you would probably start out with an outline like this:

int binarysearch(int x, int[] xs) {
    int lo = 0;
    int hi = xs.length;
    while (lo < hi)
        ...
    return -1; // x not found
}

Then you stop to think what should go in the loop. Well, I need to find the mid point. If the item I'm looking for is less than middle, I go left. If it's greater, I go right. If it's the same, I've found what I'm looking for. So you write:

    int mid = (hi + lo)/2;
    if (x < xs[mid]) hi = mid;
    else if (x > xs[mid]) lo = mid;
    else return mid;

Yep that looks about right. You test it and it works. But some time later you find that your program gets stuck in an infinite loop with some inputs. Bummer, I guess the stop condition should be lo < hi-1. That solves the infinite loop, but now it returns the wrong answer from time to time...

It's time to deactivate autopilot and practice mindful programming: actually thinking about what you're doing. This means thinking carefully about questions like:

  • What do the variables actually mean?
  • What is the stopping condition?
  • What invariants should be maintained in the loop? Is progress towards the stopping condition guaranteed?

Let's apply this approach here. Variables:

  • lo: first index in subarray being searched.
  • hi: first index after subarray being searched. (Half-open intervals tend to work very well.)
  • mid: splits the subarray into two halves. If the size is odd, make the first half smaller; in other words mid = (lo+hi)/2.

As for the stopping condition, the search can succeed as long as there's at least one element in the subarray. With these definitions of variables, that's lo < hi.

How about the loop invariants? On each iteration, if we get lucky and find the element the loop should exit. If the element is not found, the subarray should become smaller to avoid an infinite loop.

If you now look at the code from before, you'll see it's correct on all accounts except maybe the last: Suppose the subarray has size n. When x > xs[mid], the new subarray ranges from mid to hi, which makes its size ceil(n/2). This explains the infinite loop: if n = 1, ceil(n/2) = 1, and the loop makes no progress at all.

When x > xs[mid], we don't want to look at xs[mid] again, so we can exclude it from the search by setting lo = mid+1. This makes the size of the new subarray ceil(n/2)-1, which is guaranteed to be less than n.

The correct* binary search therefore stands:

int binarysearch(int x, int[] xs) {
    int lo = 0;
    int hi = xs.length;
    while (lo < hi) {
        int mid = (hi + lo)/2;
        if (x < xs[mid]) hi = mid;
        else if (x > xs[mid]) lo = mid + 1;
        else return mid;
    }
    return -1; // x not found
}

*) Not truly correct if it's possible that computing hi + lo overflows in your programming language. In that case use lo + (hi - lo)/2 or something similar.