Binary search and its variants in interviews
Classic: find a target in a sorted array in O(log n). Variants: first/last occurrence, lower/upper bound, search in rotated sorted array, search the answer (binary search on a predicate over a range — capacity, threshold). The pattern is 'monotonic predicate over an index range'.
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."
Follow-up questions
- •How do you find the first and last occurrence of a target?
- •How does binary search on rotated sorted array work?
- •Give an example of 'binary search the answer'.
Common mistakes
- •`(l + r) / 2` overflow (academic in JS but conceptual).
- •Mixing closed and half-open intervals → infinite loop.
- •Failing to update l/r correctly when arr[m] equals target in bound searches.
Performance considerations
- •O(log n) time, O(1) space. Variants on the answer search are O(log(range) × cost(feasible)).
Edge cases
- •Empty array.
- •Target smaller than all / larger than all.
- •All duplicates.
Real-world examples
- •Autocomplete index lookup, virtualized list scroll-to-index.
- •Capacity planning / threshold finding via 'search the answer'.