Searching in PHP SCRIPT PHP

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.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

PHP Topics