Binary Search — Why Everyone Gets It Wrong (Off-By-One)

Binary search is 10 lines, invented in 1946 — and studies found most programmers write it with bugs. The bugs are always boundaries.

The template that never fails

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {                        // ≤ not < !
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;   // +1, or infinite loop
    else                    hi = mid - 1;   // -1, or infinite loop
  }
  return -1;
}

The three bug factories

• while (lo < hi) misses the last candidate when lo === hi
• lo = mid (without +1) loops forever on 2-element ranges
• Java/C++ trivia: (lo+hi)/2 can integer-overflow; safe form is lo + (hi-lo)/2 (JS numbers don't overflow this way, but say it in interviews)

It's more than finding values

Variants: first/last occurrence, rotated sorted array, "binary search the answer" (min capacity, min speed problems). All the same skeleton with a different condition.

Test your version against our hidden test cases — the empty array and 2-element cases catch most implementations.