# Writing a Binary Search

^{12}/Dec 2016

# 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 `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;
}
```