Searching

Searching: Is That Song in My Library? Linear Search, One Song in a Million, in 20 Looks: Binary Search.

Updated

  1. 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.
  2. 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.