Binary Search Is Deeper Than You Think

Most people I talk to think binary search is for one thing. You have a sorted array, you want to find a number, you cut the range in half each time. That's the picture in their head and that's where it ends.

I used to think the same. But the more problems I did, the more I realized the sorted array thing is just one version of it. The real thing binary search needs isn't that the array is sorted. It just needs the answer to flip in one direction and stay flipped.

The shape that actually matters

Imagine an array that looks like this.

[false, false, false, false, true, true, true]

Once it turns true, it never goes back. That's all binary search really wants. As long as your sequence has that shape, you can find the boundary (the first true, or the last false) in log time instead of walking through every item one by one.

And once you see it like that, the "find a number" problem becomes just a special case. Asking "is arr[i] >= x?" turns the sorted array into false, false, ..., true, true. You're just looking for the first true. Nothing new.

A problem that doesn't look like search

Here's a small one I like.

You have an array that started as [1, 2, 3, 4, 5, ..., N]. Someone picked one number, removed it, and slid everything after it down by one. So if they removed 3 from a length-7 array, you now have [1, 2, 4, 5, 6, 7]. Find which number was removed.

If you just walk the array, that's O(N). Fine. But you can also use binary search, because there's a hidden monotonic property here.

Let check(i) = (arr[i] == i), with 1-based indexing.

For the array above:

index:  1  2  3  4  5  6
arr:    1  2  4  5  6  7
check:  T  T  F  F  F  F

True, true, then false forever. That's our shape. The first index where check is false is exactly the missing number. So you binary search for it.

lo = 1
hi = N - 1
 
while lo < hi:
  mid = (lo + hi) / 2
  if arr[mid] == mid:
    lo = mid + 1
  else:
    hi = mid
 
# arr[lo] != lo, so the removed number is lo

It's not a search problem on the surface. There's no target, nothing to "find" in the usual sense. But the monotonic shape is there, so binary search works.

The CCTV thing

The cleanest version of this idea I've seen happened to a friend. She lost something at a café and the place had a few hours of CCTV. She didn't want to scrub through all of it.

Think about what the footage actually is. Early on, the thing is there. Later on, it's gone. Somewhere in the middle, it transitioned from present to missing, exactly once. Present, present, present, ..., gone, gone, gone.

Same shape again. So you can just binary search on time.

lo = start of footage
hi = end of footage
check(t) = "is the item still visible at time t?"
 
while lo < hi:
  mid = (lo + hi) / 2
  if check(mid):
    lo = mid + 1
  else:
    hi = mid

About a dozen scrubs and you've narrowed a four-hour video down to the exact moment it disappeared. And usually, whoever was standing next to it.

So

The sorted array is just the most boring version of binary search. The real trick is noticing the shape. Anytime you can ask a yes-or-no question whose answer flips once and stays flipped, binary search is on the table, even if the problem doesn't look like searching at all.