php中实现二分法查找的程序代码

二分法（dichotomie） 即一分为二的方法. 设[a，b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点.

例子1

header('Content-Type: text/html; charset=utf-8;');

$arr = array(2,33,22,1,323,321,28,36,90,123);
sort($arr);

//二分法查找
echo $index = binarySearch($arr,321);

function binarySearch($arr,$key){
 $len = count($arr);
 $mid = -1;
 $start = 0;
 $end   = $len-1;

 while($start<=$end){
  $mid = (int)(($start+$end)/2);
  echo $mid."n";
  if($arr[$mid] == $key){
   return $mid;
  }else if($arr[$mid] < $key){
   $start = $mid+1;
  }else if($arr[$mid] > $key){
   $end = $mid-1; 
  }
 }
}

例子2

//search函数 其中$array为数组，$k为要找的值，$low为查找范围的最小键值，$high为查找范围的最大键值
function search($array, $k, $low=0, $high=0) 
{
    if(count($array)!=0 and $high == 0)     //判断是否为第一次调用
    {
        $high = count($array);
    }
    if($low <= $high)        //如果还存在剩余的数组元素
    {
        $mid = intval(($low+$high)/2);      //取$low和$high的中间值
        if ($array[$mid] == $k)       //如果找到则返回
        {
            return $mid;
        }
        elseif ($k < $array[$mid])      //如果没有找到，则继续查找
        {
            return search($array, $k, $low, $mid-1);
        }
        else
        {
            return search($array, $k, $mid+1, $high);
        }
    }
    return -1;
}
$array = array(4,5,7,8,9,10);       //测试search函数
echo search($array, 8);        //调用search函数并输出查找结果
?>