Binary Search algorithm advanced implementation in PHP

Created:17 Feb 2020 00:41:03 , in  Maths,  Web development

In this article I look at what's known as Binary Search algorithm and provide its advanced implementation in PHP programming language. This is the second part of the series on the algorithm.

In the first part (main/index/binary-search-algorithm-implementation-in-php) I gave a brief explanation on how Binary search algorithm finds searched for value, presented a concise implementation written in PHP and provided examples of use.

Broadly speaking, this part follows the same format. Below you are going to find an (extended) implementation of Binary Search algorithm in PHP and a few varied examples of its use to get you accustomed with this beast and its configuration.

This new, extended version of Binary Search does everything the aforementioned earlier version can do. However, unlike its tiny brother, it returns an array ( possibly of many values if they were found to be the same as the searched for one). Crucially, the extended implementation can also use user defined comparison function, which is an extremely useful and powerful feature for complex custom searches. More details on both features are found in the examples section below.

Advanced Binary Search in PHP

PHP class called SWWWBinarySearch consists of two static functions. Single is a basic Binary Search implementation mentioned above and described in the first part of this series. Multi is the advanced implementation of the algorithm most of this article is about. The basic version has been included to ensure completeness of SWWWBinarySearch class.

/**
 * SWWWBinarySearch - Recursive Binary Search algorithm implementations
 * Author: S.Wojnowski
 * Licence GNU v3
 */
 class SWWWBinarySearch{
  private function __construct(){}

  /**
   * Recursive single value return binary search implementation
   * Arguments:
   *   A - array - array of values to search in
   *   $key - string / number - value to search for
   * Return: string / number if search succeeds, false if it fails
   * 
   */ 
  public static function single(&$A,$key,$start = 0,$end = NULL){

    if(!isset($end)){
      if(count($A) === 0){
        $end = 0;
      } else { 
        $end = count($A) -1;
      }  
    } 

    if($start <= $end){
      $mid = (int)floor(($start + $end) / 2);

      switch($key <=> $A[$mid]){
        case 0:
          return $A[$mid];
        case -1:
          return self::single($A,$key,$start,$mid-1);  
        case 1:
          return self::single($A,$key,$mid+1,$end); 
      } 
    } else {
      return false; 
    }
  }

  /**
   * Recursive single/multiple value return Binary Search implementation
   * Arguments:
   *   A - array - array of values to search in
   *   $key - string / number - value to search for
   *   $cmpFunc - function - user defined function whose arguments are $a - $key, $b - item in A
   * Return: array (empty if search fails)
   * 
   */
  public static function multi(&$A,$key,$cmpFunc = false,$start = 0,$end = 0){
     
    if(!$cmpFunc){
      $cmpFunc = function($a,$b){return $a <=> $b;}; 
    }

    if(!isset($start)){
      $start = 0;
    }

    if(!$end){
      $end = count($A) - 1;
    }

    if($start <= $end){
      if(($start + $end) % 2 === 0 ){
        $mid = ($start + $end) / 2;
      }else{
        $mid = (int)ceil(($start + $end - 1) / 2);
      } 

      switch($cmpFunc($key,$A[$mid])){
        case 0:
          $needles = [];
         
          $needles[] = $A[$mid]; 

          // forward look for similar values
          if(isset($A[$mid+1])){
            for($i = $mid+1; $i < count($A) -1 ; $i++ ){
              $compResult = $cmpFunc($key,$A[$i]); 
              if($compResult === 0){
                $needles[] = $A[$i];
              } else 
                if($compResult === -1){
                  break; 
                } 
            }
          }

          // backwards look for similar values 
          if(isset($A[$mid-1])){
            for($i = $mid-1; $i > 0 ; $i-- ){
              $compResult = $cmpFunc($key,$A[$i]); 
              if($compResult === 0){
                $needles[] = $A[$i];
              } else 
                if($compResult === 1){
                  break; 
                } 
            }
          }

          return $needles;
        case -1:
          return self::multi($A,$key,$cmpFunc,$start,$mid-1); 
        case 1:
          return self::multi($A,$key,$cmpFunc,$mid+1,$end); 
      } 
    } else {
      return [];
    }
  }

}

Sort it before searching

As mentioned in the first part of this series, Binary Search algorithm operates on sorted array. All the example below conform to this requirement.

Advanced Binary Search examples

Quick number search

First example is about searching for a single integer in an array of integers. You might already know it from the first part of this series. The advanced search uses a built-in comparison function for searches like this and returns an array with a single value in it if search was successful or empty array if it was not.

$A = [1,2,3,4,5,6];
$key = 5; // searched for value
SWWWBinarySearch::multi($A,$key);
=> [5]

Multiple valued returns and custom comparison functions

Second example is about searching in an array of arrays with possible multiple identical searched for values.

This example uses a user specified comparison function.

Specifically, in this example I'm looking for creatures with 6 legs.

$animals = [
  [
    'species' => 'dog',
    'legs' => 4
  ],
  [
    'species' => 'cat',
    'legs' => 4
  ],
  [
    'species' => 'caterpillar',
    'legs' => 6
  ],
  [
    'species' => 'ant',
    'legs' => 6
  ],
  [
    'species' => 'spider',
    'legs' => 8
  ],
  [
    'species' => 'crab',
    'legs' => 10
  ],
];

$key = 6; // a 6 legged animals are being searched for 
    
// comparison function
$cmpFunc = function($a,$b){   
  return $a <=> $b['legs'];  
};

// search
SWWWBinarySearch::multi($animals,$key,$cmpFunc) ;
   
=>
[
  [
    'species' => 'caterpillar',
    'legs' => 6
  ],
  [
    'species' => 'ant',
    'legs' => 6
  ],
];

In the third example I'm searching for a species in $animals, whose name has length 4. Notice, that $animals has been sorted by number of characters in each species' name, and, that a custom comparison function is in use here again.

$animals = [
  [
    'species' => 'dog',
    'legs' => 4
  ],
  [
    'species' => 'cat',
    'legs' => 4
  ],
  [
    'species' => 'ant',
    'legs' => 6
  ],
  [
    'species' => 'crab',
    'legs' => 10
  ],
  [
    'species' => 'spider',
    'legs' => 8
  ],
  [
    'species' => 'caterpillar',
    'legs' => 6
  ],
];

// comparison funtion for comparing species name length
$cmpFunc = function($a,$b){
  return $a <=> strlen($b['species']);  
};

// search 
SWWWBinarySearch::multi($animals,4,$cmpFunc);

=>     
[
  [
    'species' => 'crab',
    'legs' => 10
  ]
]

Searching for objects

In this example array $tennisPlayers being searched in contains object representing tennis players. The objects are instances of this class:

class TennisPlayer{
  public $name;
  public $atp;

  public function __construct($conf){
    $this -> name = $conf["name"];
    $this -> atp = $conf["atp"]; 
  }
}

the objects in $tennisPlayers are sorted by ATP ranking:

$tennisPlayers = [
    new TennisPlayer(['name' => 'Novak Djokivic','atp' => 1]),
    new TennisPlayer(['name' => 'Stefanos Tsitsipas','atp' => 6]),
    new TennisPlayer(['name' => 'Gael Monfils','atp' => 9]),
    new TennisPlayer(['name' => 'David Goffin','atp' => 10]),  
    new TennisPlayer(['name' => 'Stan Wawrinka','atp' => 13]),
    new TennisPlayer(['name' => 'Cristian Garin','atp' => 26]),
    new TennisPlayer(['name' => 'Filip Krajinovic','atp' => 39])
];

Firstly, I'll try to find tennis player(s) whose ATP ranking is between 6 and 20 inclusive.

// comparison function for players with ATP ranking between 6 and 20
$cmpFunc = function($a,$b){
  if($b -> atp >= $a['top'] and $b ->atp <= $a['bottom']){
    return 0;
  }

  if($a['top'] < $b -> atp){
      return -1; 
  }
     
  if($a['top'] > $b -> atp){
    1;
  }

  if($a[0] < $b -> atp){
    return -1;  
  }  
};

// search 
SWWWBinarySearch::multi($tennisPlayers,['top' => 6,'bottom' => 20],$cmpFunc);

The return value is an array of 4 players, whose names are: Stefanos Tsitsipas,Gael Monfils,David Goffin and Stan Wawrinka.

The last example aims at finding a tennis player by name and returning its ATP ranking:

To conduct a valid search, $tennisPlayers has to be sorted by tennis player name rather than his ATP ranking:

// usort uses user defined comparison function for sorting
usort($tennisPlayers,function($a,$b){
  return $a -> name <=> $b -> name; 
});

Next, I need a comparison function which compares required value ($key) and each player's name:

$cmpFunc = function($a,$b){
  return $a <=> $b -> name;  
};

// search for Stan Wawrinka and return his ATP ranking
SWWWBinarySearch::multi($tennisPlayers,'Stan Wawrinka',$cmpFunc)[0] -> atp
=> 13

Conclusion

I hope, the various examples given in this article have helped you to understand and appreciate how powerful advanced Binary Search algorithm implementation described in this article can be. With it, if something is comparable (not necessarily 3-ways, 2 will do), it is also searchable and findable in time amount other search algorithms can't match. You just need to specify a suited-to-your-needs comparison function and make sure that the array you searching in is sorted.

This post was updated on 17 Feb 2020 01:29:50

Tags:  php ,  recursion