Binary search

Halve the problem, every step

Twenty probes find one item among a million; thirty among a billion. The requirement is that the array is sorted — and that is the catch, because sorting it costs n log n, so binary search pays off when you search many times and sort once.

function search(a, target) {
  let lo = 0;
  let hi = a.length - 1;            // INCLUSIVE — so the loop is <=

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

The three bugs

Jon Bentley reported that in his courses, given as much time as they wanted, about 90 % of professional programmers failed to write a correct binary search. It is twelve lines. Pick one convention and hold it: hi inclusive, lo <= hi, always move past mid.

• Overflow. (lo + hi) / 2 overflows once the indices are large. The famous version of this bug was in the Java standard library for nine years. lo + ((hi - lo) >> 1) cannot overflow, and it is the same number.
• The off-by-one in the loop. If hi is inclusive the condition is lo <= hi; if hi is exclusive (a.length) it is lo < hi and the update is hi = mid, not mid - 1. Mixing the two conventions gives a loop that misses the last element, or one that never ends.
• Not moving. lo = mid instead of lo = mid + 1 is an infinite loop the moment lo and hi are adjacent, because mid rounds down to lo. Every iteration must shrink the range.

The variants you actually need

lowerBound is more useful than plain search, because it answers all of these at once: where would this go if I inserted it; how many items are smaller; what is the first item that is at least this. upperBound (the first index where a[i] > target) gives you the other end, and upperBound − lowerBound is how many copies of the target there are.

Note that this version never tests equality. It finds a boundary, which is why it works on duplicates where a plain search returns an arbitrary one of them.

/* lower bound: the first position where a[i] >= target.
   Returns a.length if every item is smaller. */
function lowerBound(a, target) {
  let lo = 0;
  let hi = a.length;                 // EXCLUSIVE here

  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;                   // keep mid as a candidate
  }

  return lo;
}

Searching an answer, not an array

This is the generalisation worth taking away. Any time the answer is a number, and "does x work?" is monotonic — false, false, false, true, true — you can binary search the answer space without an array existing at all. Rate limits, buffer sizes, capacity planning, "how many machines do we need": all the same twelve lines.

/* the smallest speed that finishes the job in time */
function smallestThatWorks(lo, hi, works) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (works(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

When not to

• A small array. Below about 50 items a linear scan is faster: it is cache-friendly and branch-predictable, and binary search jumps around memory.
• An unsorted array searched once. Sorting costs n log n to save n; just scan.
• When a hash table fits. Exact-match lookups are O(1) there. Binary search wins when you need range queries — "everything between these two dates" — which a hash cannot answer at all.