Version: 2.0
Type: Function
Category: Algorithms
License: GNU General Public License
Description: Binary search algorithm function. Takes an array as an argument and the element to be searched for in the array. Returns ‘1’ if found, ‘0’ if not. The code can be modified slightly to return the array index of the found element.
/* Author: J.B.Lamer, Date: 20070321
*
* binarysearch performs a search on an already sorted (by value) array
* returns false on not found ( check with '===' )
* and position otherwise
*/
function binarysearch( $haystack, $needle )
{
if ( !is_array($haystack) )
{ return false; }
$btm = 0;
$top = count($haystack)-1;
// just in case not a normal array, but is sorted properly
$keys = array_keys($haystack);
while ( $btm <= $top )
{
$pivot = floor(($btm+$top)/2);
if ( $needle == $haystack[$keys[$pivot]] )
{ return $keys[$pivot]; }
elseif ( $needle < $haystack[$keys[$pivot]] )
{ $top = $pivot-1; }
else
{ $btm = $pivot+1; }
}
return false;
}
