Searching
Checking every locker versus playing guess my number: linear search, binary search on sorted data, and the off-by-one traps that catch everyone at first.
Updated
Searching
- Is That Song in My Library? Linear Search (Apprentice): Answer "is this song in my library, and where?" for a list kept in the order the songs were added: the search every list supports, what it costs, and the size at which it stops being fast enough.
- One Song in a Million, in 20 Looks: Binary Search (Apprentice): Find one song among a million in about 20 looks, on every keystroke: why checking every song, jumping to the first letter and skipping ahead by 1,000 all fall short, and the search that fixes them, binary search, written so it's right at the edges.
Exercise: Find the Song
- Exercise: Find the Song (Apprentice): A music app's search box freezes on a million songs: write the catalog's search so it reads at most 20 titles, keep the playlist search that reads from the top, count what each one reads, and let the tests check them, edge cases and 10,000 searches included.