Data structures and patterns · Question 38 of 50

How does binary search work, and when can you use it?

What they're checking

Getting the boundaries right, and spotting "binary search on the answer".

The answer

On sorted data, compare with the middle element and throw away the half that cannot hold the answer: O(log n), so a million items take about 20 steps. The bugs are at the edges: with lo <= hi, move to mid - 1 and mid + 1 (or use one consistent half-open style), and compute mid = lo + (hi - lo) / 2 rounded down; in languages with fixed-size integers, (lo + hi) / 2 can overflow.

It works on anything monotonic, not only arrays: the first bad version, the smallest capacity that ships all the parcels in D days, an integer square root. That is "binary search on the answer".

function search(a, target) {
  let lo = 0, hi = a.length - 1
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2)
    if (a[mid] === target) return mid
    if (a[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}

The picture

[1  3  5  7  9  11  13]    looking for 11
 lo       mid        hi    7 < 11: go right
             lo  mid  hi   11: found in 2 steps
The follow-up they'll ask

How do you find the first of several equal values?

Show the answer

When you find a match, remember mid and keep searching to the left (hi = mid - 1).

Your progress stays on this device.