computer-science/linear-vs-binary-search-why-30-guesses-can-beat-a-billion.md
Linear vs binary search: why 30 guesses can beat a billion
Need to find one item in a list? You can check every item in turn (linear search), or, if the list is sorted, look at the middle and throw away half each time (binary search).
The difference is enormous. On a billion items, linear search may need a billion checks; binary search never needs more than 30, because doubling the list adds just one step.
Play guess-my-number, race both methods side by side, and read a short Python version of each.
$ ls computer-science/
see all →
computer-science/heaps-how-a-computer-always-knows-the-most-urgent-item-without-sorting.md
Heaps: how a computer always knows the most urgent item without sorting everything
A hospital waiting room, a game's task list and a map app all need the same thing: the most urgent item, right now, while new items keep…
computer-science/coin-change-why-grabbing-the-biggest-coin-first-can-fail-and-how-a-tab.md
Coin change: why grabbing the biggest coin first can fail, and how a table fixes it
A cashier owes 6 cents and has coins worth 1, 3 and 4. Grabbing the biggest coin first uses three coins, but two 3s do it in two. This…
computer-science/binary-search-trees-why-the-order-you-insert-numbers-changes-how-fast.md
Binary search trees: why the order you insert numbers changes how fast you can find them
A binary search tree keeps numbers in order with one rule: smaller goes left, bigger goes right. Build one yourself, watch a search light…
computer-science/merge-sort-how-splitting-a-list-in-half-again-and-again-sorts-it-with.md
Merge sort: how splitting a list in half again and again sorts it with far less work
How do you sort 10,000 numbers without making millions of comparisons? Merge sort never sorts a big pile. It splits the list until every…
computer-science/hash-tables-how-a-computer-finds-one-name-among-thousands-without-chec.md
Hash tables: how a computer finds one name among thousands without checking them all
Your phone finds one contact among thousands without reading them all. The trick is a hash table: a row of numbered slots and a small…
computer-science/stacks-and-queues-why-undo-takes-the-newest-item-and-a-printer-takes-t.md
Stacks and queues: why undo takes the newest item and a printer takes the oldest
Press undo and the last thing you typed disappears first. Send documents to a shared printer and the first one is printed first. Both are…