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, until the search item is found (or not).

Note

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), the list involved in the search must first be sorted, which of course downgrades performance.

How to do it...

We first construct a search class, Application\Generic\Search, which accepts the primary list as an argument. As a control, we also define a property, $iterations:

namespace Application\Generic;
class Search
{
  protected $primary;
  protected $iterations;
  public function __construct($primary)
  {
    $this->primary = $primary;
  }

Next we define a method, binarySearch(), which sets up the search infrastructure. The first order of business is to build a separate array, $search, where the key is a composite of the columns included in the search. We then sort by key:

public function binarySearch(array $keys, $item)
{
  $search = array();
  foreach ($this->primary as $primaryKey => $data) {
    $searchKey = function ($keys, $data) {
      $key = '';
      foreach ($keys as $k) $key .= $data[$k];

      return $key;
    };
    $search[$searchKey($keys, $data)] = $primaryKey;
  }
  ksort($search);

We then pull out the keys into another array, $binary, so that we can perform the binary sort based on numeric keys. We then call doBinarySearch(), which results in a key from our intermediary array $search, or a Boolean, FALSE:
```
  $binary = array_keys($search);
  $result = $this->doBinarySearch($binary, $item);
  return $this->primary[$search[$result]] ?? FALSE;
}
```
The first doBinarySearch() initializes a series of parameters. $iterations, $found, $loop, $done, and $max are all used to prevent an endless loop. $upper and $lower represent the slice of the list to be examined:
```
public function doBinarySearch($binary, $item)
{
  $iterations = 0;
  $found = FALSE;
  $loop  = TRUE;
  $done  = -1;
  $max   = count($binary);
  $lower = 0;
  $upper = $max - 1;
```

We then implement a while() loop and set the midpoint:

  while ($loop && !$found) {
    $mid = (int) (($upper - $lower) / 2) + $lower;

We now get to use the new PHP 7 spaceship operator, which gives us, in a single comparison, less than, equal to, or greater than. If less, we set the upper limit to the midpoint. If greater, the lower limit is adjusted to the midpoint. If equal, we're done and home free:
```
switch ($item <=> $binary[$mid]) {
  // $item < $binary[$mid]
  case -1 :
  $upper = $mid;
  break;
  // $item == $binary[$mid]
  case 0 :
  $found = $binary[$mid];
  break;
  // $item > $binary[$mid]
  case 1 :
  default :
  $lower = $mid;
}
```
Now for a bit of loop control. We increment the number of iterations and make sure it does not exceed the size of the list. If so, something is definitely wrong and we need to bail out. Otherwise, we check to see whether the upper and lower limits are the same more than twice in a row, in which case the search item has not been found. Then we store the number of iterations and return whatever was found (or not):
```
    $loop = (($iterations++ < $max) && ($done < 1));
    $done += ($upper == $lower) ? 1 : 0;
  }
  $this->iterations = $iterations;
  return $found;
}
```

How it works...

First, implement the Application\Generic\Search class defining the methods described in this recipe. Next, define a calling program, chap_10_binary_search.php, which sets up autoloading and reads the customer.csv file as a search target (as discussed in the previous recipe):

<?php
define('CUSTOMER_FILE', __DIR__ . '/../data/files/customer.csv');
include __DIR__ . '/chap_10_linked_list_include.php';
require __DIR__ . '/../Application/Autoload/Loader.php';
Application\Autoload\Loader::init(__DIR__ . '/..');
use Application\Generic\Search;
$headers = array();
$customer = readCsv(CUSTOMER_FILE, $headers);

You can then create a new Search instance, and specify an item somewhere in the middle of the list. In this illustration, the search is based on column 1, customer name, and the item is Todd Lindsey:

$search = new Search($customer);
$item = 'Todd Lindsey';
$cols = [1];
echo "Searching For: $item\n";
var_dump($search->binarySearch($cols, $item));

For illustration, add this line just before switch() in Application\Generic\Search::doBinarySearch():

echo 'Upper:Mid:Lower:<=> | ' . $upper . ':' . $mid . ':' . $lower . ':' . ($item <=> $binary[$mid]);

The output is shown here. Notice how the upper, middle, and lower limits adjust until the item is found:

Table of Contents for
PHP 7: Real World Application Development

Building a binary search class

Note

How to do it...

How it works...

See also

Table of Contents for PHP 7: Real World Application Development

Building a binary search class

Note

How to do it...

How it works...

See also

Table of Contents for
PHP 7: Real World Application Development