Halving the Search Space

Play "guess my number" between 1 and 100. You don't guess 1, 2, 3, ... You guess 50, hear "higher", guess 75, and so on. Every answer throws away half of what's left.

That's binary search. On a sorted list you look at the middle element and compare it with the target. Whichever half can't contain the target is gone, and you repeat on the other half.

find 23
nums:  2  5  8 12 16 23 38 56 72 91
       lo          mid            hi
16 < 23  -> drop the left half (and mid)

nums:  .  .  .  .  . 23 38 56 72 91
                     lo    mid    hi
56 > 23  -> drop the right half (and mid)

nums:  .  .  .  .  . 23 38  .  .  .
                     lo hi
                     mid -> 23, found!

What binary search really needs. Not "sortedness" as such, but a yes/no question whose answers flip exactly once as you move right:

index:           0  1  2  3  4  5  6
nums:            1  3  4  7  9 11 15
nums[i] >= 7 ?   F  F  F  T  T  T  T
                          ^ the boundary

A question like that is called monotonic. If you can look at one position and know which side of the boundary it's on, you can halve. That opens doors far beyond sorted arrays:

• "Can Koko finish the bananas at speed k?" is false for small k and true for big k.
• "Is version v bad?" flips once, at the first bad version.
• In a rotated sorted array, "is nums[i] <= nums[-1]?" flips once, at the minimum.

Interview signals: the input is sorted (or was, before a rotation); the prompt demands O(log n); or you're asked for the smallest/largest value that "still works" over a huge range like 1..10^9.