Binary search is logarithmic search over a monotonic structure. The interview value isn't the classic — it's recognizing the variants.

1. Classic binary search

function bsearch(arr, target) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (arr[m] === target) return m;
    if (arr[m] < target) l = m + 1;
    else r = m - 1;
  }
  return -1;
}

Use (l + r) >> 1 or l + Math.floor((r - l) / 2) — avoids large-number overflow concerns in other langs.

2. Lower bound / upper bound

Find the first index where arr[i] >= target (lower bound) — the canonical "where would I insert this?" That gives you first-occurrence, last-occurrence, count-of-target.

function lowerBound(arr, target) {
  let l = 0, r = arr.length;            // [l, r)
  while (l < r) {
    const m = (l + r) >> 1;
    if (arr[m] < target) l = m + 1;
    else r = m;
  }
  return l;
}

The half-open interval [l, r) is the cleanest mental model — fewer off-by-ones.

3. Search in rotated sorted array

One half is always sorted. Check which, decide which side to recurse.

4. Binary search the answer (a predicate)

The most powerful variant: binary search over a value range, not an index, when there's a monotonic predicate ("can I do X with budget B?").

• Capacity to ship packages within D days.
• Smallest divisor such that sum ≤ threshold.
• Minimum speed to finish in time.

let l = lo, r = hi;
while (l < r) {
  const m = (l + r) >> 1;
  if (feasible(m)) r = m;
  else l = m + 1;
}
return l;

When to reach for it

• Sorted input, or monotonic predicate over a range.
• "Find first / smallest / minimum-that-works".
• O(n) feels too slow; O(log n) is plausible.

Interview framing

"Binary search applies whenever there's a monotonic structure — a sorted array, or a yes/no predicate that flips exactly once over a value range. I prefer the half-open [l, r) form because it generalizes cleanly to lower-bound, upper-bound, and 'search the answer' variants. The trick is recognizing the predicate even when the input isn't literally sorted."