Build a Database from Zero (Part 4): Get Sorted, Binary Search — and Why Inserting Hurts

• Solve the "range" problem a hash table couldn't — with a sorted array;
• Build binary search yourself: find an exact value in O(log n), and sweep a range cheaply;
• Realize a hidden cost by yourself: inserting into a sorted array must shift everything, which is exactly the pain that will drive you to a tree.

• Know Part 3: a hash table nails equality but can't do ranges, because it never orders keys;
• Be comfortable with simple loops and a bit of splice-style shifting.

A hash table was great — but only for price === 50. The moment you ask price < 50, it's helpless. So what's missing?

The answer is hiding in plain sight: if the data were sorted, "less than 50" would be a window, not a hunt. A sorted structure lets you "land near a value" and then walk.

So the move is obvious: keep the rows sorted by the field you search on. Let's do exactly that.

If our books are kept sorted by price, then "under 50" isn't a full sweep — it's "start at the front, walk until prices exceed 50." And crucially, finding a specific value stops being O(n).

But how do you find it fast? You can't just guess the index. You need a way to zero in. That's binary search.

The idea is the classic "guess the middle, decide which half." Each probe discards half the candidates.

Why is this O(log n)? Because every step halves the remaining range. 100k items → 50k → 25k → ... → done in about 17 steps. That's the geometric magic: doubling the data adds only one step.

Binary search alone is nice, but the reason databases love sorted structures is ranges. Watch: to get "price < 50," you don't find one item, you find where the boundary is, then walk.

Two nice properties fall out:

• Exact lookup: binarySearch → O(log n);
• Range: find one boundary with lowerBound, then sweep a contiguous run → you only touch the results, not the whole table.

That's the payoff of "sorted." It fixed what the hash table couldn't.

But you paid a price. When you insert a new row, where does it go? By the sorted field — and that means everything after it must shift to make room.

In the worst case that's O(n) — a single insert might move 100k entries. Over many inserts, that's brutal. So here's the dilemma you've now carved out with your own hands:

• Unsorted (Part 1): inserts are cheap, but any search is O(n).
• Sorted (Part 4): searches are O(log n) and ranges are cheap, but inserts are O(n) and must shift.

You want searches fast and inserts fast. No array can do both. History's answer to "is there a structure that does both?" is a tree — and that's Part 5.

1. Count the steps: run binarySearch on 1 million sorted numbers for a few targets, and log how many times the loop ran. Confirm it's ~20, not ~1M.
2. Do a range sweep: use lowerBound to answer price >= 30 && price < 60, and print how many rows you visited — compare it to scanning all rows.
3. Feel the insert pain: keep a 100k-element sorted array, time a single splice insert in the middle, then time 1000 of them. Note how it degrades.

• Sorted data turns "hunt" into "window" — the key to range queries;
• Binary search halves the range each step → O(log n) exact lookup;
• lowerBound finds the boundary, then you sweep only the results → cheap ranges;
• The tradeoff: inserts must shift = O(n) — which is the flaw that pushes us toward a tree.

Keywords: sorted array、binary search、O(log n)、range query、lower bound、insertion cost O(n)

You've now seen it from both sides: the hash table is fast but range-blind; the sorted array handles ranges but insertion is O(n). So you've been forced into a genuinely interesting question: is there a structure where both find and insert are cheap?

That's the story of the tree — and specifically the structure real databases actually use by default, the B+ tree, which is Part 5.