Binary Search

Given a sorted array and a target, return the target's index, or -1 if it's absent. (LC 704)

Binary search is famously easy to describe and famously easy to get subtly wrong — the classic result is that a majority of professional implementations have had an off-by-one somewhere. The fix is not memorizing code; it's holding one invariant.

The recipe

Say before you type: "The answer, if it exists, is always inside [lo, hi]. Every step I probe the middle and discard the half that can't contain it — including the probe itself."

1. lo = 0, hi = length - 1 — inclusive bounds.
2. Loop while lo <= hi — with inclusive bounds, lo === hi is still one real candidate.
3. Probe the middle. Match → return it.
4. Middle too small → the answer is strictly right of it: lo = mid + 1. Too big → hi = mid - 1. Either way the probed element leaves the range.

The code

function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;            // INCLUSIVE bounds
  while (lo <= hi) {                           // <= because lo==hi is a real candidate
    const mid = lo + Math.floor((hi - lo) / 2); // never overflows; floor for TS
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;      // discard left half INCLUDING mid
    else                    hi = mid - 1;      // discard right half INCLUDING mid
  }
  return -1;
}

Why this shape

Sorted data gives you a superpower: comparing the target against one element tells you about half the array. Each comparison discards half the remaining candidates, so the range shrinks n → n/2 → n/4 → … → 1 in log₂(n) steps. A million elements is ~20 probes.

Everything else in the template exists to protect the invariant. mid + 1 / mid - 1 matter because the probed element has been ruled out — leave it in the range and [lo, hi] can stop shrinking, which is the classic infinite loop.

Complexity

	Cost	Because
Time	O(log n)	The candidate range halves every iteration
Space	O(1)	Two pointers, no recursion

Traps

• Compare the element you probed. The classic slip is computing mid and then comparing nums[lo] or nums[hi] instead of nums[mid]. The vicious part: most test cases still pass — it only breaks when the target sits on the far side of the probe ([1,2,3,4,5] seeking 2 quietly returns -1). The rule: probe middle, compare middle, discard on middle.
• mid is an average, not a difference. lo + (hi - lo) / 2, floored. Writing (hi - lo) / 2 alone points at the wrong element whenever lo > 0.
• Return the index, not the value. After twenty minutes of pointer discipline, the return line is where attention lapses.
• Write two or three "target on the far side" tests. The bugs above survive happy-path testing.

The variants — memorize the shape, not the problem

Leftmost insertion point / first index ≥ target (lowerBound). Note the exclusive hi and that mid stays a candidate:

function lowerBound(nums: number[], target: number): number {
  let lo = 0, hi = nums.length; // EXCLUSIVE hi
  while (lo < hi) {             // < because hi is not a candidate
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else                    hi = mid; // keep mid as a candidate
  }
  return lo; // insertion index; nums[lo] is the first >= target
}

Binary search on the answer. When the array isn't what's sorted — the answer space is. Define a monotonic feasible(x) (false…false, true…true) and find the first true. This is Koko Eating Bananas (LC 875), Split Array Largest Sum (LC 410), Ship Packages in D Days (LC 1011):

function minFeasible(lo: number, hi: number, feasible: (x: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (feasible(mid)) hi = mid;
    else               lo = mid + 1;
  }
  return lo;
}

Time O(n log range) — one feasibility check per probe, log₂ over the answer range.

The pattern this trains

"Sorted array" in a prompt → binary search or two pointers. But the senior version of the trigger is broader: anything monotonic is binary-searchable — a sorted array, a rotated one, or an answer space where "can we do it with x?" flips from no to yes exactly once.