Writing a Binary Search

Background

As I am preparing for interviews recently, this is a good time to write about my experience in writing a binary search. Please correct me if I get anything wrong in the content.

Binary Search

Binary search is always one of the most popular algorithms and at the same time tough to implement correctly. It is surprisingly hard to find a correct while easy-to-modify binary search code out there.

In the book Programming Pearls, the author mentioned that only 10% of the programmers can write a bug-free binary search.

Here I will discuss my experience in writing it and highlight some common mistakes in implementing the algorithm.

Example Problem

Let’s say we want to find the first target in an array.

e.g. Finding the index of the first 5 in the array [1, 2, 3, 4, 5, 5, 6]. The answer is 4 (0-based).

Approach

Invariant

The key to write a correct binary search is to maintain (and keep in mind of) a loop invariant which will be true at the beginning and the end of each loop as suggested in Programming Pearls.

For example, let’s call the array A, target target, lower bound lo and upper bound hi. We want an invariant A[lo] <= target <= A[hi] and lo < hi. A natural pick of lo and hi will be 0 and N-1 where N is the size of A.

The loop condition is lo < hi because it looks most natural. It means when the size of search space is larger than 1, continue to search.

Transition

The existence of the invariant facilitates the development of the rest of the algorithm. The next important decision is the transition in each round of the loop.

The variable mid is at the center of lo and hi, intuitively, (lo + hi) / 2 (this is buggy, but we’ll fix this later).

There are 2 cases. - if A[mid] >= target - target must be in the range A[0..mid]. In order to maintain the invariant, the transition will be hi = mid. - else, i.e. A[mid] < target - As the target is not in A[0..mid], we’ll discard this range, making the transition lo = mid + 1.

Loop Termination & Verification

When lo < hi does not hold, the loop terminates.

Will it always terminate? Yes, because either lo increases or hi decreases in each round. There is still a trick though, please see section Dead Loop.

The loop terminates even if there does not exist a solution. We’ll have to verify it. It is a simple if-then-else statement. The final search index is stored in lo.

• if A[lo] == target
  • exists a solution
• else
  • no solution

Traps

Integer Overflow

Problem

This can be hard to observe but when the result of lo + hi exceeds the limit of integer, things will go wrong.

Solution

The solution is to change

mid = (lo + hi) / 2

to

mid = lo + (hi - lo) / 2

Dead Loop

Problem

Let’s say now we want to find the last index of the target in the array A.

e.g. Finding the index of the first 5 in the array [1, 2, 3, 4, 5, 5, 6]. The answer is 5 (0-based).

Following the steps above, we’re tempted to change the algorithm as follows:

• if A[mid] <= target
  • lo = mid
• else, i.e. A[mid] > target
  • hi = mid - 1

However, this creates dead loop because of the integer division in the calculation of mid.

For example, in the case of lo = 0, hi = 1 and A[mid] <= A[lo], the algorithm will loop between mid = lo + (hi - lo) / 2, A[mid] <= target and lo = mid until the end of the world.

The core of the problem is that the statement “either lo increases or hi decreases in each round” is not true any more. lo may stay unchanged under certain conditions.

Attempt

The solution is to change mid = lo + (hi - lo) / 2 to mid = lo + (hi - lo + 1) / 2 (beware: integer overflow again!) such that the division will round up instead of round down.

Final Solution

This quick solution suffers from integer overflow again because when hi = INT_MAX and lo = 0, hi - lo + 1 will overflow. The fix would look like mid = lo + (hi - lo) / 2 + (hi - lo) % 2.

Final Values

Problem

We have lo, mid and hi in our algorithm. Which one should we use as the answer?

Solution

In our case of our loop condition lo < hi, we can safely conclude that when the statement evaluates to false, lo is equal to hi. Of course, this also depends on how the transition is written.

Anyway it is still much easier to understand than something like lo <= hi and lo < hi - 1 because lo and hi will be different when the algorithm terminates.

Variants

There are many variants of binary search. Finding first target, finding last target, finding the first value greater than target, finding the first value smaller than target, etc. These are left as an exercise.

Hopefully with the above tips in mind, it will be easier to write a bug-free and readable binary search.

Full Code

Here is the full code of the original “find first target” problem in C++:

int binary_search(vector<int> A, int target){
    int N = A.size();
    int lo = 0, hi = N - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (A[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return A[mid]==target?lo:-1;
}

References

1. Binary Search - topcoder
2. Programming Pearls by Jon Bentley