php中实现二分法查找的程序代码-PHP源码-PHP中文网

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

php中文网

发布： 2016-06-08 17:19:49

原创

1564人浏览过

二分法查找在高级点的开发可能会用到了，当然在大公司找工作时都会有面试题是这种了，下面我们来看一篇关于二分法查找在php中实现方法，具体的细节如下所示。

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

例子1

TURF(开源)权限管理系统

TURF（开源）权限定制管理系统（以下简称“TURF系统”），是蓝水工作室推出的一套基于软件边界设计理念研发的具有可定制性的权限管理系统。TURF系统充分考虑了易用性，将配置、设定等操作进行了图形化设计，完全在web界面实现，程序员只需在所要控制的程序中简单调用一个函数，即可实现严格的程序权限管控，管控力度除可达到文件级别外，还可达到代码级别，即可精确控制到

查看详情

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   $mid = (int)(($start+$end)/2);
  echo $mid."\n";
  if($arr[$mid] == $key){
   return $mid;
  }else if($arr[$mid]    $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     {
        $mid = intval(($low+$high)/2);      //取$low和$high的中间值
        if ($array[$mid] == $k)       //如果找到则返回
        {
            return $mid;
        }
        elseif ($k         {
            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函数并输出查找结果
?>