Tag Archive for 'iterative binary search'

PHP Iterator Design Pattern II: Binary Search

Published on January 3, 2014 by Bill Sanders in Binary Searches, Iterator and Raspberry PI. 0 Comments Tags: , , , , , , , , , .

fastBinaryList 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.QuizbinaryBtnDownload
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:

?View Code PHP 
< ?php
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

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

?View Code PHP 
< ?php
//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.
Continue reading ‘PHP Iterator Design Pattern II: Binary Search’