Software Engineer interview question
When is binary search the right approach?
Binary search fits a monotonic predicate over an ordered search space: once the predicate changes, it never changes back. Maintain explicit low/high invariants and handle boundaries to avoid off-by-one errors.
Direct answer
What a strong answer covers
How it works
Binary search applies whenever the answer space can be ordered so that a yes-or-no question is false up to some point and true after it. Classic sorted-array lookup is one case; searching for the smallest capacity that satisfies a constraint, the first version where a test fails, or the largest value that fits a budget are the same shape. The implementation keeps two bounds with a stated invariant about which side has been ruled out, moves one bound per iteration, and checks the termination condition and empty ranges explicitly to avoid off-by-one errors.
Example
Finding the first commit that broke the build is a binary search over commit history because once the build is broken it stays broken; git bisect does exactly this. Allocating the minimum ship capacity to deliver packages in D days is a binary search over capacity values, because if capacity C works then every larger capacity works too.
Common mistakes
- Applying it to data that is not sorted or a predicate that is not monotonic.
- Writing mid = (low + high) / 2 in a language where the sum overflows.
- Getting the loop condition wrong and returning the wrong boundary or looping forever.
A useful answer structure
Answer from your own work.
Do not memorise a script: use only examples you can explain honestly in follow-up questions.
Open the desktop workspace and rehearse a clear answer in your own words.