Binary Search algorithm implementation in PHP

Created:16 Feb 2020 00:43:24 , in  Maths,  Web development

In this article I take a closer look at a very efficient search algorithm called Binary Search. I implement it in PHP programming language and provide example usage for searches done on arrays of common data. This article is the first part of the two. In the second part I give a more powerful implementation of the algorithm, which can use user defined functions for comparisons and returns multiple values if they happen to be the same in the searched array.

Sort before you search

Binary Search is a powerful algorithm, which searches for a value in a an array. The values in the array have to be sorted first, thought. Make sure you do that. This blog provides an article on how to search various types on data in a array (Search form is your best friend here). Examples above all have presorted arrays.

How Binary Sort works

Binary sort algorithm uses divide and conquer technique. It takes an array of values and works on its indices by systematically narrowing down range of them by a half. The algorithm finds the middle index of array in the range it is working on and checks whether the searched for values is at the index, if it is, the algorithm returns it. If the value is less than the value at the index, only indices from 0 to middle index -1 are searched at the next pass. Otherwise, indices between middle index + 1 and array length - 1 are searched at the next pass. The algorithm uses recursion to search for required value, and narrow down range of indices to check until their difference is 0. When it reaches the difference and the value still has not been found, the value is not in the array and the search fails.

Binary Search in PHP

The implementation of the basic Binary Search algorithm relies heavily on combined comparison operator (<=>) and recursion.

/**
 * SWWWBinarySearch - Recursive Binary Search algorithm implementations
 * Author: S.Wojnowski
 * Licence GNU v3
 */

class SWWWBinarySearch{
  private function __construct(){
  
  }

  /**
   * Recursive single return value binary saerch 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; 
    }
  }
}         

Binary Search example usage

Here are some basic searches done with SWWWBinarySearch::single. The implementation can handle arrays of: numbers, strings, arrays and object. The input array, as said above, must be sorted first.

$A = [1,2,13,19,25,66];
$key = 19; // searched for value
print_r(SWWWBinarySearch::single($A,$key));
=> 19

$A = [0xA,0xB,0xC,0xFA,0xFF,735];
$key = 735; // searched for value
print_r(SWWWBinarySearch::single($A,$key)); 
=> 735

$A = [1911,1923,1933,1967,1980,2019];
$key = 1950; // searched for value
print_r(SWWWBinarySearch::single($A,$key));
=> false //failed search

$A = [[1,2,3],[1,2,4],[1,2,6],[2,5,7],[3,5,6],[4,4,4]];
$key = [2,5,7];
print_r(SWWWBinarySearch::single($A,$key));
=>  [2,5,7] // short version of printed value

Conclusion

As of version 7.0 has the combined comparison operator (<=>). With it implementing algorithms relying on comparisons, like Binary search algorithm, has become much easier than in previous version of the language. Add recursion to the mix and you have pretty much built your Binary Search algorithm in minutes.

In the second part of this series I describe the aforementioned more advanced version of Binary Search, which has some very useful features.

I hope you have found this article useful, informative and interesting, or at least interesting and informative ;).

This post was updated on 16 Feb 2020 01:40:52

Tags:  php ,  recursion