Binary Search

Your app worked last week. Today it crashes, and 1,000 changes were made in between. You could test each change in order until you hit the first broken one. Or you could test change 500. If the app already crashes there, the culprit is in the first half; if not, it is in the second half. One test just ruled out 500 changes. Ten tests in total will pin it down.

That is binary search. It works because the changes have a shape: every change before the culprit is fine, and every change from it onward is broken. Fine, fine, fine, broken, broken. You are looking for the boundary.

#The idea: find the first "yes"

A sorted array has the same shape. Take [3, 8, 8, 8, 12, 15, 20, 27] and ask, for each position, "is this value at least 8?" The answers are no, yes, yes, yes, yes, yes, yes, yes. All the "no"s come first, then all the "yes"s, because the array is sorted.

The position of the first "yes" is called the lower bound of 8. It is the most useful single answer binary search can give you:

• If the value there equals 8, it is the first 8 in the array.
• If it does not, 8 is not in the array, and this is where you would insert 8 to keep the array sorted.
• If every answer is "no", the lower bound is n, one past the end.

To find it, keep two positions, lo and hi. Everything left of lo is known to be "no". Everything from hi onward is known to be "yes". The positions you have not decided yet are [lo, hi): lo is included, hi is not. Check the middle of that range, then throw away the half that cannot hold the first "yes".

#Lower bound, traced

Find the lower bound of 8. Watch what happens when the search lands on an 8: it does not stop, because an earlier 8 might exist.

lo = 0, hi = nwhile lo < hi:  mid = lo + (hi - lo) // 2  if a[mid] < target: lo = mid + 1  else: hi = midreturn lo

#The template

Learn this one function well. Almost every binary search on an array is this function, or a small change to the comparison.

// First index i with a[i] >= target, or a.length if there is none.
// a must be sorted from low to high.
function lowerBound(a, target) {
  let lo = 0;
  let hi = a.length; // half-open range [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < target) lo = mid + 1; // mid is a "no": answer is right of it
    else hi = mid;                     // mid is a "yes": answer is mid or left
  }
  return lo; // lo === hi
}
 
function contains(a, target) {
  const i = lowerBound(a, target);
  return i < a.length && a[i] === target;
}
 
lowerBound([3, 8, 8, 8, 12, 15, 20, 27], 8); // 1

# First index i with a[i] >= target, or len(a) if there is none.
# a must be sorted from low to high.
def lower_bound(a, target):
    lo, hi = 0, len(a)  # half-open range [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1  # mid is a "no": answer is right of it
        else:
            hi = mid      # mid is a "yes": answer is mid or left
    return lo  # lo == hi
 
def contains(a, target):
    i = lower_bound(a, target)
    return i < len(a) and a[i] == target
 
lower_bound([3, 8, 8, 8, 12, 15, 20, 27], 8)  # 1

Every piece of the template is there for a reason:

• hi = n, not n − 1. The answer can be n ("everything is smaller"), so the range has to be able to end there.
• while lo < hi. The loop runs while the unknown range [lo, hi) has something in it. When lo == hi, the answer is pinned.
• mid rounds down, so mid is always at least lo and always less than hi. It is a real index inside the range.
• lo = mid + 1 on a "no", because mid itself is ruled out. hi = mid on a "yes", because mid might be the answer and must stay at the edge. Either way the range shrinks, so the loop always ends.

#One template, many questions

Change the question from "at least target" to "greater than target" and you get the upper bound: the first index after all copies of the target. The only change is < to <=.

// First index i with a[i] > target, or a.length.
function upperBound(a, target) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
 
const a = [3, 8, 8, 8, 12, 15, 20, 27];
upperBound(a, 8) - lowerBound(a, 8); // 3 copies of 8
upperBound(a, 8) - 1;                // 3: the last 8
lowerBound(a, 13);                   // 5: insert 13 here

# First index i with a[i] > target, or len(a).
def upper_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
a = [3, 8, 8, 8, 12, 15, 20, 27]
upper_bound(a, 8) - lower_bound(a, 8)  # 3 copies of 8
upper_bound(a, 8) - 1                  # 3: the last 8
lower_bound(a, 13)                     # 5: insert 13 here

Python ships both as bisect.bisect_left (lower bound) and bisect.bisect_right (upper bound). JavaScript has no built-in, so keep the template handy.

#Common mistakes

#Check yourself

#What to practise next

Notice that the template never needed an array. It only needed a yes/no question whose answers go no, no, …, yes, yes. Binary Search on the Answer uses exactly this template to search over possible answers, such as "the smallest speed that is fast enough".