Core PHP Programming, Third Edition

21.5. Indexing

By sorting the data, you spend time up front, betting it will pay off when you need to search. But even this searching costs something. A binary search may take several steps. When you need to do hundreds of searches, you may look for further improvement in performance. One way is to perform every possible search beforehand, creating an index. A lot of work is done at first, which allows searches to be performed fast.

Let's explore how we can transform the binary search in Listing 21.6 into a single lookup. We want an array that, given a name, returns its position in the original array, so we'll build a list of matches. Refer to the code in Listing 21.7. We won't bother sorting the list. It won't help, because we will be visiting ...