binary-search.md

Binary search is very easy to mess up. Here's my intuition - with it, my binary searches work first time, every time, with no off-by-ones.

This is loosely based off of We Need To Talk About Binary Search, which is a great explanation but is a bit finicky with its +1s, -1s and best_so_fars.

• Binary search is about finding when a predicate function flips. That is, below a certain unknown value it's always false/true, and above that it's always the other value.
  • Visually, it's a step function but you don't know where the "step" is.
• Write your predicate. Actually write it out - define a function and everything. It makes the code for the binary search much nicer to read and reason about. We'll get into examples of predicates below.
• The loop invariant for binary search is pred(lo) is one fixed value and pred(hi) is the other value, where lo is your lower bound and hi is your upper bound.
• Choose your lower bound (lo) and upper bound (hi).
  • Already have both bounds? It's possible that one of the invariants might fail - evaluate pred on the bounds if needed, and handle that case.
  • Only have one of the bounds? Take your known bound and start going towards the other bound with powers-of-2 sized jumps. This is called exponential search.
  • Don't have either of the bounds? Choose an arbitrary value and evaluate pred on it to figure out whether it's lo or hi, and then use exponential search to find the other one.
• As long as there are values between lo and hi…
  • Find the midpoint between lo and hi. I like to always use mid = lo + (hi - lo) / 2 - it prevents integer overflow and guarantees lo <= mid <= hi for floats.
  • Evaluate pred(mid), then assign mid to one of lo or hi to maintain the invariant.
• You're done! You now know the exact place where the predicate flips from false to true. Use the value that makes the most sense!

Some useful tips:

• If you're binary searching over indices of an array, set lo = -1 and hi = len(arr) and assume they satisfy the invariant. pred is actually never explicitly evaluated on the initial values of lo and hi, so you don't need to add bounds checks to pred if you do this. You might need to check for those values after the search if pred never flipped during your search!
• Binary searching over floating point numbers (including "integers" in JS over Number.MAX_SAFE_INTEGER == 2**53 – 1) is tricky! The easiest way I've found to check "if there are floats between lo and hi" is to check if mid is equal to either lo or hi.

As an example, let's search for the first instance of the number 6 in a sorted array arr:

def first_6(arr: list[int]) -> int | None:
  # What's the predicate?
  # First 6… if we use
  def pred(i: int) -> bool:
    return arr[i] >= 6
  # then `pred` will flip from false to true right before the first 6 is seen.

  # Skip the initial invariant check as described above.
  lo = -1
  hi = len(arr)

  # While there are values between…
  while hi - lo >= 2:
    # …set `lo` or `hi` to `mid` to maintain the invariant.
    # It's guaranteed that `hi - lo >= 2`, so `mid >= lo+1` and `hi >= lo+2`.
    mid = lo + (hi - lo) // 2
    if pred(mid):
      hi = mid
    else:
      lo = mid

  # We're interested in the first place that `pred` is true, which is `hi`.
  # But it might be possible that `hi == len(arr)` if all the values in `arr`
  # evaluated to false (i.e. all below 6).
  if hi == len(arr):
    return None

  # Now let's use `hi`. It might be possible that 6 isn't in `arr`, so we should
  # check the index:
  if arr[hi] != 6:
    return None
  return hi

What about last 6?

def last_6(arr: list[int]) -> int | None:
  # What's the predicate?
  # Last 6… if we use
  def pred(i: int) -> bool:
    return arr[i] <= 6
  # then `pred` will flip from true to false right after the last 6 is seen.

  # Skip the initial invariant check as described above.
  lo = -1
  hi = len(arr)

  # While there are values between…
  while hi - lo >= 2:
    # …set `lo` or `hi` to `mid` to maintain the invariant.
    # It's guaranteed that `hi - lo >= 2`, so `mid >= lo+1` and `hi >= lo+2`.
    mid = lo + (hi - lo) // 2
    if pred(mid):
      lo = mid
    else:
      hi = mid

  # We're interested in the last place that `pred` is true, which is `lo`.
  # But it might be possible that `lo == -1` if all the values in `arr`
  # evaluated to false (i.e. all above 6).
  if lo == -1:
    return None

  # Now let's use `lo`. It might be possible that 6 isn't in `arr`, so we should
  # check the index:
  if arr[lo] != 6:
    return None
  return lo

What about calculating sqrt(n) badly through binary search?

import math


def bad_sqrt(n: float) -> float:
  # Let's assume `n` is sensible.
  if not math.isfinite(n) or n < 0.0:
    raise ValueError("seriously?")

  # What's the predicate? If we use
  def pred(m: float) -> bool:
    return m*m >= n
  # then `pred` will flip from false to true right before the square root.

  lo = 0.0
  # Wait a minute… `pred(lo)` could be true!
  if pred(lo):
    # That means n is 0.
    return n

  # What should a good `hi` be? Intuitively
  hi = n
  # but we know that sqrt(n) > n if 0 < n < 1, so
  if hi < 1.0:
    hi = 1.0
  # Then `pred(hi)` should always be true.

  # While there are values between…
  # (You can also do `while math.nextafter(lo, hi) != hi`.)
  while True:
    mid = lo + (hi - lo) / 2
    if lo == mid or mid == hi:
      break

    # …set `lo` or `hi` to `mid` to maintain the invariant.
    if pred(mid):
      hi = mid
    else:
      lo = mid

  # We're interested in the first time `pred` is true.
  return hi

As promised, the three functions above were written on my first try. You can test them out for yourself!