Explain binary search and its common variations used in coding interviews.
Binary search seems simple but has many subtle variations that interviewers love to test. Off-by-one errors are the most common bug. This question assesses whether you truly understand the invariants and can adapt binary search to non-obvious problems.
Start with standard binary search on a sorted array: O(log n) time, O(1) space.
Cover lower bound (first occurrence) and upper bound (last occurrence) variations.
Explain binary search on a rotated sorted array — a very popular interview question.
Introduce binary search on the answer space: when you cannot search the array directly but can binary search on possible answer values.
Standard binary search finds a target in a sorted array in O(log n) by repeatedly halving the search space. The key variations are: Lower bound finds the first position where a value appears or could be inserted — I adjust by continuing to search left when I find the target. Upper bound finds the last position — I continue searching right. For a rotated sorted array like [4,5,6,7,0,1,2], I determine which half is sorted by comparing mid with left, then check if the target falls in the sorted half. Binary search on the answer space is powerful for optimization problems: for example, to find the minimum capacity to ship packages in d days, I binary search on the capacity value and check feasibility with a greedy scan. The key to getting binary search right is defining clear loop invariants: what is true about left and right at every iteration. I always use the left < right pattern and carefully decide whether to set right = mid or right = mid - 1 based on whether mid could be the answer.
Define your invariant clearly before coding: what does left represent? What does right represent?
Use the left < right loop with mid = left + (right - left) / 2 to avoid integer overflow.
Test your solution with arrays of size 0, 1, and 2 to catch off-by-one errors.
Define clear invariants for left and right boundaries. Decide upfront whether your search range is [left, right] or [left, right). Stick to one convention and test with small arrays.
Instead of searching an array, you binary search over possible answer values. For each candidate value, you check if it is feasible. This applies to problems like "minimum maximum" or "maximum minimum" optimization.
Not directly, but it works on any search space with a monotonic property — if you can define a condition that flips from false to true, you can binary search for the boundary.
HireMe AI listens to your interview in real-time, detects questions, and generates instant answer suggestions — so you never freeze up again.
Try HireMe AI Free