A colleague asked about why there is no binary search method in PHP, but only the slow linear time array_search. I don’t have answer though, but someone suggest that you can do fast searching in a hash by flipping the array into a hash:

<?php
// DON'T USE THIS FUNCTION, IT IS SLOW
function flip_search($list, $key) {
$res = array_flip($list);
if (array_key_exists($key, $res)) {
return $res[$key];
}
return FALSE;
}
?>

What’s the run time of this function? **Linear**, as there is no magic in doing the flipping, but has to go through the array entry one by one, and not to mention it is memory inefficient. So if you get a sorted array, use binary search; if your array is not sorted, use the build-in array_search

I set out to write a general binary search for PHP.

<?php
/*
* Parameters:
* $a - The sort array.
* $first - First index of the array to be searched (inclusive).
* $last - Last index of the array to be searched (exclusive).
* $key - The key to be searched for.
* $compare - A user defined function for comparison. Same definition as the one in usort
*
* Return:
* index of the search key if found, otherwise return (-insert_index - 1).
* insert_index is the index of smallest element that is greater than $key or sizeof($a) if $key
* is larger than all elements in the array.
*/
function binary_search(array $a, $first, $last, $key, $compare) {
$lo = $first;
$hi = $last - 1;
while ($lo <= $hi) {
$mid = (int)(($hi - $lo) / 2) + $lo;
$cmp = call_user_func($compare, $a[$mid], $key);
if ($cmp < 0) {
$lo = $mid + 1;
} elseif ($cmp > 0) {
$hi = $mid - 1;
} else {
return $mid;
}
}
return -($lo + 1);
}
?>

To use it is pretty straight forward:

<?php
function cmp($a, $b) {
return ($a < $b) ? -1 : (($a > $b) ? 1 : 0);
}
$a = array(1,2,3,4,5,6);
$idx = binary_search($a, 0, sizeof($a), 4, 'cmp');
?>

Feel free to use the code if you need it.

### Like this:

Like Loading...

*Related*

“-($lo + 1)” can be written as “~$lo”

Thanks, You’ve saved me time writing it myself and then testing 🙂

thanks, saved me too 🙂

$compare may default to a function (eg: ‘strcmp’)

and maybe called as variable function avoiding call_user_func:

$compare($a[$mid], $key)

cast to integer and division by 2 maybe avoided too:

$mid = (($hi – $lo) >> 1) + $lo;

I also like to use pre{inc|dec}rement operators where + – 1 is needed:

$lo = ++$mid;

$hi = –$mid;

Thanks for your suggestions.

With the call_user_func, it can calls both standalone function as well as class methods (either static or instance).

forget about pre{inc|dec}rement, my mistake

Fatal error: Call to undefined function binary_search()

please write correct program

<?php

function cmp($a, $b) {

return ($a $b) ? 1 : 0); }

$a = array(1,2,3,4,5,6);

$idx = binary_search($a, 0, sizeof($a), 4, ‘cmp’);

?>

`binary_search`

is not a build-in function in PHP. If you want to use it, you have to include it in your code.Pingback: Jeff Slutz - Binary Search Algorithm for PHP

can you please give an example of a form and binary search action in php?

why are you using function inside the loop. Can’t we compare using operator only. It is more efficient.

public static function binarySearch($niddle, array $haystack, $sort = false)

{

if ($sort)

{

sort($haystack);

}

$low = 0;

$high = count($haystack) – 1;

while ($low <= $high)

{

$mid = (int)(($low + $high) / 2);

if ($haystack[$mid] == $niddle)

{

return $mid;

}

if ($niddle $haystack[$mid])

{

$low = $mid + 1;

}

}

return -1; //not found

}

The user function is for caller to define the comparison, rather than hardcoding it.