PHP 7 Programming Cookbook

Building a binary search class

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, ...