How does binary search work?

Binary search maintains a range of candidate indices. It checks the midpoint, then discards the half that cannot contain the answer. The hard part is not the idea; it is keeping the boundaries and loop condition consistent so the algorithm terminates and does not skip the answer.

function lowerBound(values, target) {
  let left = 0;
  let right = values.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (values[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

Avoiding the classic bugs

• Use left + Math.floor((right - left) / 2) to avoid overflow in fixed-width languages
• Decide whether the range is inclusive or half-open and stay consistent
• Make sure every branch shrinks the range
• For first or last occurrence, do not return immediately on a match

Binary search also applies to monotonic answer spaces, not just arrays. If a predicate is false up to some point and true afterwards, you can binary search for the boundary. That is the basis of problems such as minimum capacity or minimum speed.