Binary Search Is an Invariant

Binary search is famous for being easy to get almost right. The honest reason: most people memorize a loop instead of stating an invariant — a sentence that stays true about the range at every step. Choose the sentence first, and every disputed detail (< or <=? mid or mid + 1?) stops being a judgment call and becomes a consequence.

The closed-range invariant

The classic form maintains: the target, if it exists, is inside [low, high] — both ends included.

export function binarySearch(sorted: number[], target: number): number {
  let low = 0
  let high = sorted.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    const guess = sorted[mid]

    if (guess === target) return mid
    if (guess < target) low = mid + 1
    else high = mid - 1
  }
  return -1
}

The loop condition is <= because a one-element window low === high is still a legal range — it has a member you have not examined. Writing < quietly declares an unexamined element "not there", which is why < fails exactly on the boundary cases: first element, last element, a target that lands where the window narrows to one. Every move shrinks the window past the midpoint (mid + 1, mid - 1) because mid itself was just examined and answered — moving onto it re-examines a settled cell and, worse, can make the window stop shrinking, which is the infinite-loop variant of this bug.

while (low  high) {
  const mid = Math.floor((low + high) / 2)
  if (sorted[mid] === target) return mid
}

The general form: the insertion point

"Where would this go?" is the more powerful question, because "is this there?" is a special case of it. The general form maintains a half-open invariant: everything before low is less than the target, everything from high on is at least the target.

export function insertionIndex(sorted: number[], target: number): number {
  let low = 0
  let high = sorted.length

  while (low < high) {
    const mid = Math.floor((low + high) / 2)
    if ((sorted[mid] as number) < target) {
      low = mid + 1
    } else {
      high = mid
    }
  }
  return low
}

Notice what changed with the invariant: the loop is now < (an empty range [low, low) has no members, so it ends the search), high starts past the end (the insertion point may be after everything), and the shrink is high = mid — never mid - 1 — because mid failed the "less than" test, so it belongs to the right partition and cannot be discarded past itself. When the loop ends, low === high is the count of elements smaller than the target, which is simultaneously: the insert position, the index of the first equal element, and the answer to "how many came in under this value". One function, three interview questions.

if ((sorted[mid] as number) < target) {
  low = mid + 1
} else {
  high = 
}

Binary search on an answer, not an index

The pattern generalizes past arrays. If a question has the shape "what is the smallest value of X such that some check passes", and the check is monotone — once true, true forever — then the answer space is a sorted array you cannot see, and binary search walks it. Minimum capacity that ships the cargo in D days, maximum eating speed that finishes the pile in H hours: the check is a greedy simulation, the search is the code above with sorted[mid] replaced by mid itself. Recognizing that a question has this shape is worth more than memorizing any specific instance of it.

How to debug one

A wrong binary search lies quietly — it returns an index that exists. So make the invariant loud: print low, high, mid and the invariant's claim every iteration, and check by hand that the discarded side really is discardable. An infinite loop means the window stopped shrinking — look for a move that lands on mid. A missed boundary means the loop condition disagrees with the invariant — write the invariant out as a sentence, then let the condition read it back to you. In the exercises for this concept, the failing tests are precisely the boundaries: first element, last element, absent-below, absent-above.

Where this bites

• Mixing invariants. A <= condition with high = mid moves can skip the window empty past a live element; a < condition with mid - 1 can spin forever. Counter: pick closed or half-open, and derive condition and moves together — they are one decision, not three.
• high = sorted.length in the closed form. The closed range's last legal index is length - 1; using length reads one past the end on the first probe. Counter: the invariant sentence says "both ends included" — an index that is not a member cannot be an end.
• Duplicated targets and "found it". The classic form returns some index of a duplicate, and callers that assume the first one build subtle bugs. Counter: when order among equals matters, use the insertion-point form — it is deterministic by construction.
• Searching an unsorted range. The discard argument needs the midpoint to speak for its half. Counter: the first question is always "what property makes one comparison enough to drop half the space?" — sortedness, monotone check, or nothing.