php 二分法查找函數 使用教程

二分法查找函數的php實現

/*
*
* binarysearch 在數組中查找制定值
* returns false 沒找到( 使用 '===' 作比較)
* return position 找到
*/
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;
}