Binary Search
Prompt
We have a sorted list of version timestamps and need to look one up fast — the list is big enough that a linear scan shows up in our latency budget. Walk me through how you'd find a target timestamp's index.
How this round runs
The spec is thin on purpose — clarify what "find" means and what to return when it's missing before you code, and expect me to bend a constraint once you have a clean version working.
Model answer
Clarify first: is the list guaranteed sorted and free of duplicates? If the
target isn't present, do I return -1, or the insertion point? Are we searching
by value or by index?
Binary search halves the search space each step — O(log n) time, O(1)
space, versus the O(n) linear scan. The whole game is the loop invariant: the
target, if present, always lives in [left, right] inclusive. Keep that true and
the off-by-ones take care of themselves.
function search(arr, target) {
let left = 0;
let right = arr.length - 1; // inclusive bound
while (left <= right) { // still a candidate while left == right
const mid = left + Math.floor((right - left) / 2); // overflow-safe
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1; // discard mid and the left half
else right = mid - 1; // discard mid and the right half
}
return -1;
}
Two invariant-driven choices: left <= right (not <), because when they're
equal there's still one unchecked element; and mid +/- 1, so we always shrink
the window and never loop forever on the element we just rejected.
Dry-run on [1, 3, 5, 7, 9], target 7: left=0, right=4, mid=2, arr=5 < 7 so
left=3; mid=3, arr=7, found, return 3.
- Asked whether duplicates exist and what to return when the target is absent
- Stated the loop invariant (target stays within [left, right]) and tied the off-by-ones to it
- Used an overflow-safe mid and explained left <= right vs left < right
- Dry-ran the index updates on a concrete array
- Now return the first (or last) occurrence when duplicates exist → keep searching the left (or right) half after a match instead of returning immediately
- What if the array was sorted then rotated? → find the sorted half each step and decide which side the target is in