Example of a recursive binary search that returns the index rather than boolean.
<?php
// returns the index of needle in haystack
function binSearch($needle, $haystack)
{
// n is only needed if counting depth of search
global $n;
$n++;
// get the length of passed array
$l = count($haystack);
// if length is 0, problem
if($l <= 0)
{
return -1;
}
// get the mid element
$m = (($l+($l%2))/2);
// if mid >= length (e.g. l=1)
if($m >= $l)
{
$m = $m-1;
}
// get the indexed element to compare to the passed element and branch accordingly
$compare = $haystack[$m];
switch(true)
{
case($compare>$needle):
{
// recurse on the lower half
$new_haystack = array_slice($haystack, 0, $m);
$c = count($new_haystack);
$r = binSearch($needle, $new_haystack);
// return current index - (length of lower half - found index in lower half)
return $m - ($c - $r);
break;
}
case($compare<$needle):
{
// recurse on the upper half
$new_haystack = array_slice($haystack, $m, ($l-$m));
$c = count($new_haystack);
$r = binSearch($needle, $new_haystack);
// return current position + found index in upper half
return $m + $r;
break;
}
case($compare==$needle):
{
// found it, so return index
return $m;
break;
}
}
}
?>