Basis Lab

Answers · Making it fast enough

Why does binary search only work if the list is sorted?

In shortBecause only in a sorted list does one comparison against the middle tell you that half the items cannot be the one you want.

Because order is the only thing that turns a comparison into a deletion. Asking whether the target is bigger than the middle item gives you one fact about one item; in an ordered list that fact also settles every item to the left of it or to the right of it, which is what lets half of them be thrown away without ever being examined. In an unordered list the same comparison says nothing at all about the rest, and the half you throw away may contain the thing you are looking for.

x>a[m]  ⟹  x∉a[0],…,a[m],because a[i]≤a[m]<x for every i≤mx > a[m] \;\Longrightarrow\; x \notin a[0], \dots, a[m], \qquad \text{because } a[i] \le a[m] < x \text{ for every } i \le m

The left half is safe to discard not because the middle item happens to be smaller than the target, but because order makes the middle item the largest of that half. Run the comparison the other way and the mirror argument holds: if the target is smaller than the middle, every item from the middle rightwards is at least as large as the middle and so larger than the target, and the right half goes. Both deletions rest on the same fact, that position in the array and rank in the order agree. That is what sorted means here, and it is the whole of what the search borrows from it.

Six comparisons instead of seventy three

Take a hundred numbers in order and look for 73. The middle is 50; 73 is larger, so positions 1 to 50 are gone and 51 to 100 remain, fifty items. The middle of those is 75; 73 is smaller, so 51 to 74 remain, twenty four items. The middle is 62, then 68, then 71, each time cutting the range down to 12, then 6, then 3, and the middle of those three is 73. Six comparisons, and a scan from the front would have needed 73. Nothing about the search is clever: it is the same comparison six times over, and each one is allowed to delete a whole block because the block is ordered around the middle item.

FIG 1
steprangeitems leftmiddleverdict
11 to 1001005073 larger, keep 51 to 100
251 to 100507573 smaller, keep 51 to 74
351 to 74246273 larger, keep 63 to 74
463 to 74126873 larger, keep 69 to 74
569 to 7467173 larger, keep 72 to 74
672 to 74373found

The general count is the number of halvings kk that take nn down to one, so n/2k=1n/2^k = 1 and k=log⁡2nk = \log_2 n. That reads off as a thousand items in 10 comparisons, since 210=10242^{10} = 1024; a million in 20, since 220=1,048,5762^{20} = 1{,}048{,}576; a thousand million in 30, since 230=1,073,741,8242^{30} = 1{,}073{,}741{,}824. A scan averages half the list, so half a million against twenty at a million items. Each doubling of the data adds exactly one comparison, and that only happens because every step removes a fixed fraction of what is left rather than a fixed number of items.

The mistake is calling sorting housekeeping

The natural reading is that sorting is tidy housekeeping and the halving is the actual algorithm, so an unsorted list should still work roughly, or work with a slower constant. It fails completely, not gradually. Halving is not a search strategy on its own; it is the bookkeeping you are allowed to do once a comparison has proved that a block of items cannot contain the target. Unordered, no such proof exists, and the search discards live candidates with total confidence and no warning.

Eight numbers, in the order 10, 25, 80, 40, 5, 60, 15, 35, with 80 as the target, sitting in position 3. The middle is position 4, holding 40. Since 80 is bigger, the search keeps positions 5 to 8 and discards positions 1 to 4, and 80 was inside them. It compares against 60, then 15, and after three comparisons is down to a single item, which is 35, so it reports that 80 is not there. Every step obeyed the rule; the rule was simply never valid. Sorted, the same eight numbers are 5, 10, 15, 25, 35, 40, 60, 80, and three comparisons find 80, because each discard throws out only values that are on the wrong side of the middle by the ordering.

a=[10, 25, 80, 40, 5, 60, 15, 35],x=80  ⟹  x>a[3]=40  ⟹  discard a[0..3] and lose xa = [10,\, 25,\, 80,\, 40,\, 5,\, 60,\, 15,\, 35], \quad x = 80 \;\Longrightarrow\; x > a[3] = 40 \;\Longrightarrow\; \text{discard } a[0..3] \text{ and lose } x

Strict sortedness is not quite the deepest requirement, and this is where the rule softens. What a step actually needs is a predicate on items that is false up to some position and true after it, so that the middle's answer eliminates a contiguous block. Finding the first item at or above a value, or the boundary between expired and live records, works on exactly that basis, which is why the same routine serves a database index looking up a key range. With duplicates the predicate still holds, but you must decide whether you want the leftmost or the rightmost item equal to the target, since the plain comparison no longer distinguishes them.

Order alone is also not sufficient. The middle has to be reachable in constant time, and a sorted chain of links is not. Walking to the middle of a hundred linked items costs 50 steps, then 25 to the middle of what is left, then 12, 6, 3 and 1, which totals 97 steps, so the whole search costs about as much as scanning and the halving has bought nothing. That is the price of keeping order in a block that can be jumped into: inserting into a sorted million shifts half a million items along by one to make room. Order is cheap to use and expensive to hold, and the search only pays off where both the order and the jump are available.

Worth keeping

  • A comparison against the middle of a sorted list rules out half the list, because order makes the middle the largest of the left half and the smallest of the right.
  • Binary search takes about log base two of n comparisons, so a million items take twenty and a thousand million take thirty.
  • Order without direct access to the middle is not enough: walking to the middle of a linked list costs as much as the search saves.

Where this goes next

This question is one step of Keeping Things in Order, a course that works through its subject from the beginning. The page that teaches this part of it is Halving the Search, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. Why do databases use B-trees rather than binary search trees for indexes?Because a database index pays for disk blocks read, not comparisons made, and a wide shallow tree needs only a few block reads per lookup.
  2. How does a heap know the smallest item without keeping the whole collection sorted?A heap only keeps each parent no larger than its children, so the top is always the smallest even though the rest is not sorted.
  3. How does merge sort get n log n by splitting and merging?Splitting halves the number of runs each round, so there are about log base 2 of n rounds; merging every item once per round gives n log n.
  4. Why does inserting already sorted numbers turn a binary search tree into a linked list?Because each new number is bigger than every number already stored, so it is always attached down the right side, and the tree becomes a chain as deep as the number of items.
  5. Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
  6. Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.

Read alongside