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 15.8 into a single lookup. We want an array that, given a name, returns its position in the
original array. Our list of employees ...