PHP Iterator Design Pattern II: Binary Search

List Searches

To move ahead with implementations of the Iterator design pattern that help illustrate the value of polymorphic iterations, understanding how different list searches work is essential. In their Iterator illustration, Gamma et al provide an example of a program that has concrete iterators for both standard lists and for skip lists. Skip lists are made up of linked lists and use a binary search algorithm to quickly iterate through the skip list. So to understand skip lists you need to first understand both linked lists and binary searches. This post is dedicated to the latter—binary searches. A future post examines linked lists with skip lists.

Lists come in two basic flavors: ordered and unordered. Searches depend on finding a specific item in a list, and most algorithms are designed for ordered lists. For PHP developers, this can mean anything from searching for an item in a list from a database to an associative array. To get started, consider an associative array and finding a key using the built-in array_search($item, $list) method. The array_search(($item, $list) iterates through an array until it finds the element specified in $item in the array, $list and returns the key. To see a simple example, click the Play button and to download the file, click the Download button.
All examples were tested on single core (e.g., Raspberry Pi) and multi-core (e.g., Dell, Macintosh) systems.

Using the array_search() method, you can use the key in the key-value pairs as information resources because the search returns the key instead of the value. You can see that in the following class:

ERROR_REPORTING( E_ALL | E_STRICT );
ini_set("display_errors", 1);
//ArraySearch.php
class ArraySearch
{
    private $country;
    public function __construct($nation)
    {
         $this->country=$nation;
         //Generate list
         $currency=array('rupiah' => 'Indonesia','peso' => 'Uruguay', 'real' => 'Brazil', 'rupee' => 'India',
                         'dollar' => 'Liberia', 'euro' => 'Luxembourg', 'yen' => 'Japan', 'pound' => 'Egypt',
                         'yuan'  => 'China', 'dinar' => 'Serbia', 'shekel' => 'Israel', 'krone' => 'Norway',
                         'ringgit'  => 'Malasia', 'rial' => 'Iran', 'shilling' => 'Kenya', 'rand' => 'South Africa',
                         'ruble' => 'Belarus','dong' => 'Vietnam');
         echo "$this->country's currency is the " . array_search($this->country,$currency) . ". 
";
    }
}
$tour=$_POST['tour'];
$worker = new ArraySearch($tour);
?>

For relatively short lists, the array_search() method works fine, and you don’t have to write (or remember!) a lot of code to work with it.

The Binary Search

To get a sense of how the binary search works, take a piece of paper (a discarded joke-a-day calendar page works well) and fold it into two equal halves. Keep folding it in half until you have 6 folds. After six folds I could not get a seventh fold—the paper was too fat by that point.

Instead of doubling something, if you halve a value, even very big numbers quickly are reduced to zero. For example, how many times do you think that it would take to half the number 1 million (1,000,000), rounding all halves down, before it became zero? Would it take 1000 halves? 10,000? 100,000? The following class loops through an operation that cuts the value in half with each iteration. It starts with a value of 1 million.

//BinaryCut.php
class BinaryCut
{
    public function __construct()
    {
        $bignum=1000000;//1 million
        $count = 0;
        while($bignum > 0)
        {
            $bignum= floor($bignum / 2);
            ++$count;
            echo "iteration# $count : Number=$bignum 
";
        }
    }
}
$worker=new BinaryCut();
?>

When you run the program, you can see how quickly 1 million is reduced to zero. That same principle is used in a binary search.

Stepping though a Binary Search

A binary search requires an ordered list. To get started, consider a list from 1 to 1 00,000. If you play a guessing game with a friend and you have to guess an integer they’re thinking of by saying a number that they must tell you is higher or lower in the ordered list, you can quickly find the number using a binary search. Suppose your friend chooses 81,250. If you used a straight iteration beginning with 1, it would take 81,250 guesses! Using a binary search, you can do it in only four guesses!

With each guess, the range of values becomes half of what it was on the previous guess. It works like a vice closing in on the correct number.

Iterative Algorithm for PHP

The iterative algorithm for a binary search goes through a loop with three possible states and a state where no match is found:

• Search value and array element match
• Search value is greater than the array element
• Search value is less than the array element
• Search value is not in the array

With each iteration, it cuts the number of possible choices in half by passing the value of the previous mid value to the top or bottom of the universe of choices (originally the number of elements in the list [array]). It works like a vice as the floor comes up and the ceiling lowers.

class BinarySearch
{
    public function binarySearcher($list, $search, $size)
    {
        $low = 0;
        $high = $size - 1;
        $guess=0;
        while ( $low <= $high )
        {
            $mid = floor(($low + $high)/2);
            //State 1: The search value and array element match
            if ($list[$mid] == $search)
            {
                return $list[$mid] . " has been found in the list!"; 
            }
 
            //State 2: The array element is less than the search value
            //Raise the floor limit
            elseif ($list[$mid] < $search)
            {
                $low = $mid + 1;
                echo "Guess#" . ++$guess . "
";
            }
 
            //State 3: The array element is greater than the search value
            //Lower the ceiling limit
            else
            {
                $high = $mid - 1;
                echo "Guess#" . ++$guess . "
";
            }
        }
    //State 4: The search value is not in the list
    return "$search item was not found in this list.";
    }
}
?>

For now, the class is outside of a design pattern, but it is important to understand as a possible concrete iteration object that may have use when looking at different types of iterations for different types of lists.

Recursive Binary Search

The concept of recursion in computer science is an essential and powerful one. In a nutshell,

Recursion defines a problem in terms of itself.

If we put that in programming terms, we’d say something like,

Recursion occurs when a function (method) calls itself.

A recursion algorithm has three steps:

1. Base case (when to stop)
2. Take a step
3. Calls itself (recursion)

A simple example will help. Suppose you want to draw a line 100 pixels (dots) long. A recursive algorithm outline would look like this:

1. Stop when the line is 100 dots long
2. Add a dot
3. Draw the line

The following class shows how this would look in a PHP program:

class Recursion
{
    private $line;
    public function drawLine($length)
    {
        $this->line=$length;
        //The 'line' will be a series of 'dots.'
        if ($this->line > 0)
        {
            echo ".";
            --$this->line;
            return $this->drawLine($this->line);
        }
    }
}
$worker = new Recursion();
$worker->drawLine(100);
?>

As you can see, it can draw any size of “line” that you want. The initial instance of the Recursion object (class) invokes the drawLine() method to start the process. The method keeps calling itself until the number of dots is exhausted. With each call, it makes a slight adjustment by using a reduced number as an argument until it arrives at the base case.

You can find discussions that compare recursion versus iteration and even heated arguments as to why one is better than the other. My own personal preference is toward recursion because the solutions seem both closer to the problem and far more elegant. Those with a computer science and/or mathematical background tend toward recursive solutions. Nevertheless, I use iteration as well. The best advice I found about choosing one over the other is to look at the problem and consider which approach is most appropriate. However, if you’ve never programmed with recursion, I think you’ll find the approach to algorithm development very interesting and a lot of fun. Give it a try.

With that in mind, here is a binary search using a recursive algorithm:

class BinaryRecursive
{
    private $searchArray=array();
    private $sizeNow;
    private $mid;
    private $poke;
    private $begin;
    private $end;
    private $guess;
    private $count=0;
    private $flagUp=true;
 
    public function recursiveBinarySearch($list,$search,$size)
    { 
        $this->guess=$search;
        $this->searchArray=$list;
 
        //Only executes once 
        if ($this->flagUp)
        {
            $this->begin = 0;
            $this->end=$size-1;
            $this->flagUp=false;
        }
        //Base case
        if ($this->end < $this->begin)
        {
            return "$this->guess was not found in this list.";
        }
 
        $this->mid=floor(($this->begin + $this->end)/2);
        $this->poke=$this->searchArray[$this->mid];
 
        if ($this->poke==$this->guess)
        {
            return $this->poke . " has been found in the list!";
        }
        elseif ($this->poke > $this->guess)
        {
            $this->end = $this->mid-1;
        }
        else
        {   
            $this->begin = $this->mid+1;
        }
        echo "Guess#" . ++$this->count . "
";
        return $this->recursiveBinarySearch($this->searchArray,$this->guess,$this->end);
    }
}
?>

Both iterative and recursive binary search algorithms work the same as far a the binary reduction of universe is concerned. It works like a vice raising the floor and lowering the ceiling until the match is found as the only remaining choice.

The Binary Base

The binary search algorithm is used in many different kinds of lists and types of searches. As a basic concept, it is one of the most fundamental PHP developers need to fully grasp. The next post on this blog, Part III of this Iterator design pattern series, examines linked lists and skip lists. Skip lists rely on both linked lists and binary searches. Since PHP has built-in linked list objects, the task will be considerably easier, but making a linked lists from scratch is important to fully understand what the built-in linked lists actually do.

Until then, I welcome your comments and thoughts on these topics and how you might be able to use them in working with PHP.

Copyright © 2014 William Sanders. All Rights Reserved.