Binary Search algorithm implementation in PHP

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 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, enjoys sWWW writing computer code in PHP, JavaScript and BASH, and some other things he wrote more on on the About page of this website.

Copyrights

©Copyright, 2020 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Binary Search algorithm implementation in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/binary-search-algorithm-implementation-in-php

Add Comment

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]


I constent to processing my data given through this form for purposes of a reply by the administrator of this website.

Recent Comments

Nobody has commented on this post yet. Be first!