Ch.7: Why O(log n) Turns a Billion Rows Into 30 Steps

0:00 Binary search sounds like whiteboard vocabulary. Bisection, ordered data, all of that. But in production, the trick is simple: sorted data lets you throw half the world away. You know that whiteboard interview where they make you code binary search? Most engineers nail it, get the job, and never think about it again. Then one slow lookup path starts scanning instead of seeking, and suddenly that interview trick can be the line between a boring request and an outage. Yeah. And then they spend the next 10 years using it without realizing.

0:31 For example, your database does it on every primary-key lookup. Git bisect. Capacity planning, the kind where you ask which instance size handles your load. Binary search dressed up as a different question. So why does this primitive show up everywhere? First, it is the math. Right. O of log n is so flat at scale that it changes what is feasible. Yeah. Let me make that concrete. For example, a linear scan over a billion items is a billion comparisons. Binary search on the same billion items is, 30 Comparisons.

1:09 Wait, 30 comparisons for a billion items? 30. That is not a 10x speedup. A billion operations ties up a thread, pollutes the CPU cache, and blocks every other request that needed to be handled. 30 operations is essentially free. The difference is a request returning in microseconds versus a system timing out, dropping connections, and triggering an outage cascade. Exactly. The shock is the ratio. And the gap widens with every order of magnitude of data. Once you internalize that, you start looking for places where halving the search space is legal. In those cases, you usually want it.

1:48 The mechanical version is 6 lines. Start with a sorted array. Now look at the middle element. If it equals the target, you are done. If the target is smaller, throw away the right half. If the target is larger, throw away the left half. Then repeat on whichever half is left. Halving every step. Right. Halving every step. In 20 steps you have searched a million. The loop invariant is one sentence. If the target is in the array, it is somewhere in the active range. Every step shrinks that range by half while keeping the invariant true.

2:20 Yeah. Hmm, and yet this is the algorithm with, like, more buggy implementations in production code than I think any other. So what is the first famous trap? The middle element calculation. It looks like low plus high divided by two. Sure. That is the obvious version. It is also wrong on large arrays. If low and high are both near the maximum integer, low plus high overflows before the divide. Just like an analog odometer rolling past its maximum value and resetting to 0, the binary digits wrap around to a massive negative number.

2:56 The JDK's Arrays dot binary search had exactly that bug, and it shipped for 9 years before someone noticed. 9 years inside the standard library is the part that makes the example stick. A human error hiding inside perfect math, all because the abstraction of math runs into the physical constraints of silicon. That example sent me straight back to my own code, because I have shipped that exact mid-point formula myself, multiple times. And it is the kind of bug that, in the wrong system, would be an absolute nightmare to track down.

3:28 Right. The fix is to take high minus low, divide that by two, and add low back. Same answer mathematically. No overflow. Next, the source of bugs is mixing two different invariants in the same loop. There are three common ways to write the boundaries. Inclusive on both sides. Exclusive on both sides. Or half-open, where the low end is included and the high end is not. Each convention is valid if you keep it consistent. Wait, so the bug isn't actually in the math. It's in the human switching modes halfway through?

4:00 Exactly. The implementer started with 1 invariant and unconsciously switched. So the rule is, pick one before you write the loop and keep every boundary check, every range update, every termination condition in that same style. Right. Most of the time, half-open is the easiest to reason about. But pick the one your team already uses. So in practice, do engineers actually write this loop themselves? Almost never. Python ships the bisect module. Java ships Arrays dot binary search. C++ has standard-library bound helpers.

4:34 So the next question stops being "can I write binary search correctly," and starts being "do I know which library function I want." So the skill shifted. Right. From writing the loop to knowing which one to call. Yeah. And that is a real distinction, because bisect left and bisect right give different answers on the same array, and the difference is what most people miss. Now imagine an array that has the value 7 in it three times in a row. Bisect left tells you the index just before the first 7.

5:05 Bisect right tells you the index just after the last 7. Yeah. So if you only need to know whether 7 is in there, both work. But if you want to know how many sevens there are, you call both and subtract. The useful part is the subtraction. Bisect right minus bisect left gives the count in O of log n, with no scan. But wait, what if a reviewer says, "At 10 elements, why are we calling two library functions?" Fair pushback. At 10 elements you scan. The bisect trick wins once the array is big enough that 20 comparisons beat a thousand-element walk, which is basically anything in production.

5:44 Next, the same idea gives you ranges. Find the first position at the start value, then the first position after the end value. Slice between them. That gives every record in the date window without walking the rest of the sorted array. There is a broader boundary-search view most engineers miss. Right. Binary search is more useful for "find the first element greater than X" than it is for "is X in the array." Yeah. Because matching one value is only one use. Right. The equality check is the narrow version.

6:17 The general primitive is "split a sorted range at a boundary." Lower bound and upper bound expose that primitive directly. Once you start thinking that way, a lot of problems collapse. Take a real case: find the next event after this timestamp. Find the smallest price above a threshold. Find the first error log entry past a checkpoint. All of those are the same query. Exactly. From boundary queries, the broader pattern is binary search on the answer. Forget the array. Imagine instead a numeric range, and a yes-or-no predicate that is monotonic over that range.

6:55 Right. Honestly, I had to read this idea three times before it clicked. Monotonic meaning, once it flips from no to yes, it stays yes? Exactly. Think of it as a light switch that can only ever flip from off to on as you move from left to right across the range. There is a single boundary somewhere. The question is, where is the boundary. You find it in log of the range using the same halving trick. Pick the middle, ask the predicate, throw away the half that... Oh, right, the half that cannot contain the boundary.

7:27 The switch can be anywhere along the range. You just keep halving until you find where it flips. Yeah. Or picture the exact tipping point where water turns to ice. Water, water, water, then 32 degrees, then ice, and it stays ice as you keep dropping. The state change is monotonic. You don't have to check the colder side, you just hunt for the boundary. The array is virtual. It is whatever the predicate is sweeping over. Let's hear what that looks like in production. Let's say you have a service. You want the smallest instance size that handles peak load. The instance sizes are an ordered list.

8:03 The predicate is the load test passing or failing. Right. So you binary search over instance sizes. First, pick the middle option. Then run the load test. If it passes, throw away the more expensive half. If it fails, throw away the cheaper half. Repeat until one option is left. Yeah. 5 load-test runs can pick from 32 options. Oh, right. And that is still cheap compared with the alternatives. A real load test is, you know, 20 minutes of synthetic traffic plus warmup. 5 runs is 2 hours of capacity work.

8:34 Right. 2 hours beats the alternative, which is either guessing and over-provisioning, or running 32 load tests instead of 5. The log n savings show up most where each evaluation is expensive. Yeah. That is the difference between an afternoon of capacity work and a week of it. So where does this show up by name? Git bisect. Exactly. The most famous version of the virtual-array pattern. You know that the latest build is broken and some past build worked. Git bisect picks a commit halfway between, asks you whether the bug is present, and uses your answer to discard half the history.

9:12 Right. So the predicate is the test suite, or, you know, just an interactive yes-or-no from the developer. Right. And in log of the commit count you have the exact commit that introduced the bug. Exactly. That is binary search on a virtual array of "is the bug present at this commit." It is exactly the same machine as bisect left, just in a different shape. I love that. And here's where it really compounds. The biggest place it shows up is your database. When you query a primary key, the database walks an index, and the index is usually a B-tree.

9:51 A B-tree is binary search at every level, but with a much fatter page than the toy array version. Each layer holds hundreds of keys, so the search inside one node is itself binary search over those keys. And the path from root to leaf is, Log of the table size. So a billion-row table resolves to maybe four or 5 disk reads. If reading from RAM is like pulling a book out of your backpack, reading from disk is like walking to a library in another city. Oh, man. So the database cannot afford to walk to that library a billion times to check every row. A tiny root-to-leaf walk.

10:28 That is the payoff. Although, at hundreds of keys per node, would a linear scan inside the node be faster? They are all sitting in the same cache line, basically. For a few hundred keys, sometimes yes. Real engines benchmark it and pick. Right. Honestly, I got burned by that exactly once. A teammate accidentally dropped the index and the same query went from sub-second to 40 minutes overnight. The four-or-5-disk-read claim assumes the index is there. But the path itself, root to leaf, is binary search over levels. That part is not negotiable.

11:03 Yeah. That is why a primary-key lookup is fast and a sequential scan is not. The index turned into a binary search over levels, and the algorithm doing the work at every level is the same one we have been talking about. So we have covered where binary search wins. When is it the wrong tool? Let's hear it. Honestly? Probably more often than people think. First, on unsorted data, full stop. If your array is not sorted, you either sort first, which is O of n log n, or you scan, which is O of n. There is no shortcut.

11:37 Second, it is also wrong when the comparator is expensive and the array is small. If each compare reads from disk or makes a network call, 20 compares for log of a million can be slower than 5 compares for a 5-element scan. And it is wrong on data that is changing while you search. If another thread is appending and reordering, you cannot trust the invariant. Yeah. Binary search needs a stable, sorted view. The SRE team will tell you the same thing. They lose hours debugging stale-index tickets where a binary-search-backed cache hit returns a key the table no longer has.

12:19 If you cannot give binary search a stable view, pick a different tool. So what is the checklist? Asking for a friend who shipped that mid-point bug. Short. First, is the data sorted, or do you have a monotonic predicate? Next, is the range big enough that log of it actually pays off? Then, you know, is the comparator cheap enough that 20 calls beat 5? Finally is the data stable for the duration of the search? If the answers line up, the library function does the work. The skill is recognizing the shape, not writing the loop.

12:54 So binary search is the algorithm you stop noticing once you know where to look. Sorted data, monotonic predicate, halving step. That is the whole machine. Exactly. The whole machine. The logarithmic machine humming beneath the surface of every system you use. Next time, we look at counting sort, radix sort, and how exploiting structure in the data can beat the n-log-n barrier on comparison sorts. Yeah. Thanks for listening to Learning Podcasts.