-
Book Overview & Buying
-
Table Of Contents
PHP 7 Programming Cookbook
By :
Conventional searches often proceed through the list of items in a sequential manner. This means that the maximum possible number of items to be searched could be the same as the length of the list! This is not very efficient. If you need to expedite a search, consider implementing a binary search.
The technique is quite simple: you find the midpoint in the list, and determine whether the search item is less than, equal to, or greater than the midpoint item. If less, you set the upper limit to the midpoint, and search only the first half of the list. If greater, set the lower limit to the midpoint, and search only the last half of the list. You would then proceed to divide the list into 1/4, 1/8, 1/16, and so on, until the search item is found (or not).
It's important to note that although the maximum number of comparisons is considerably smaller than a sequential search (log n + 1 where n is the number of elements in the list, and log is the binary logarithm...