The byName function is a simpler wrapper for strcmp. Names will be ordered by
ASCIIcode. The byTitle function assigns an integer value to each title and then returns
the comparison of these integers. The bySalary function compares the wage element,
but if two employees make the same amount of money per hour, their names are
compared.
Searching
Sorting organizes information into a form that aids in finding the exact piece being
looked for. If you need to look up a phone number, it's easy to flip through the pages of a
phone book until you find the approximate area where the number might be. With a bit of
scanning you can find the number, because all the names are in order. For most of us, this
process is automatic.
If you want to duplicate this process inside a PHP script, you have to think about each of
the steps. The simplest way is to start at the beginning and look at every entry until you
find the one you want. If you get to the end and haven't found it, it must not exist. I don't
have to tell you this is probably the worst way to search, but sometimes this is all you
have. If the data are unsorted, there is no better way.
You can dramatically improve your search time by doing a binary search. The
requirement is that the data be sorted. Luckily, I've shown this to be relatively simple.
The binary search involves repeatedly dividing the list into a half that won't contain the
target value and a half that will.
To perform a binary search, start in the middle of the list. If the element in the middle
precedes the element you are searching for, you can be sure it's in the half of the list that
follows the middle element. You will now have half as many elements to search through.
If you repeat these steps, you will zero in on your targeted value very quickly. To be
precise, the worst case is that it will take log n, or the base-two logarithm of the number
of elements in the data. If you had 128 numbers, it would take at most 7 guesses. Listing
15.8 puts this idea into action.
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.