一聚教程网:一个值得你收藏的教程网站

热门教程

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

时间:2022-06-24 16:51:50 编辑:袖梨 来源:一聚教程网

二分法(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函数并输出查找结果
?>

热门栏目