Math for coding interviews/The sorted order guarantee
Binary Search: The Sorted Order Guarantee
Binary search only works because the array is sorted. Sorted order is the invariant - the thing that is always true - that lets you safely discard half the remaining elements after each comparison. If the array were unsorted, you could not know which half to keep.
See it for yourself
A sorted array with a midpoint highlighted. An arrow points left ("smaller side") and right ("larger side"). Pick a target. Is the target bigger or smaller than mid? One entire side can be safely ignored.
The sorted order guarantee
Binary search only works because the array is sorted. Sorted order is the invariant - the thing that is always true - that lets you safely discard half the remaining elements after each comparison. If the array were unsorted, you could not know which half to keep.
Think of it this way: A guessing game where I say "higher" or "lower." With 100 numbers, you can always find mine in at most 7 guesses by guessing the midpoint each time. Because log₂(100) is about 7.
For algorithms: The sorted order invariant is the heart of binary search. Recognizing when you can binary search on a problem (not just arrays - can also binary search on answer values) is a key interview skill.
Real-world analogy
A guessing game where I say "higher" or "lower." With 100 numbers, you can always find mine in at most 7 guesses by guessing the midpoint each time. Because log₂(100) is about 7.
Why it matters in interviews
The sorted order invariant is the heart of binary search. Recognizing when you can binary search on a problem (not just arrays - can also binary search on answer values) is a key interview skill.