当前位置: 代码迷 >> PHP >> 这样写二分查找如何不对呢
  详细解决方案

这样写二分查找如何不对呢

热度:41   发布时间:2016-04-28 21:27:56.0
这样写二分查找怎么不对呢

<php 
function binarySearch($arr,$a){
    
    $low = 0;
    $high = count($arr)-1;
    $mid = ceil(($low+$high)/2);

while($low<=$high){

    if($a==$arr[$mid]){
     echo "查找的数的位置是第"."$mid";
    }

    if($a>$arr[$mid]){

        $high = count($arr)-1;
     $low = $mid+1;
    $mid = ceil(($low+$high)/2);
    }

    if ($a<$arr[$mid]) {
    
     $low = 0;
     $high = $mid-1;
     $mid = ceil(($low+$high)/2);
    }
  }
}
$arr1 = array(5,7,9,10,12,16,19);
binarySearch($arr1,12);

?>

------解决方案--------------------
本帖最后由 xuzuning 于 2013-03-30 17:42:33 编辑
function binarySearch($arr,$a){
     
    $low = 0;
    $high = count($arr)-1;
    $mid = ceil(($low+$high)/2);
$n = 0;防止死循环的措施
while($low<=$high && $n++<count($arr)){
    if($a==$arr[$mid]){
        echo "查找的数的位置是第"."$mid";
        break;
    }
 
    if($a>$arr[$mid]){
 
        $high = count($arr)-1;
        $low = $mid-1;//注意这里
        $mid = ceil(($low+$high)/2);
    }
 
    if ($a<$arr[$mid]) {
         
        $low = 0;
        $high = $mid+1;//注意这里
        $mid = ceil(($low+$high)/2);
    }
  }
}
------解决方案--------------------
按 php 实际可写作
function binarySearch($arr,$a){
  $low = 0;
  $high = count($arr)-1;
  $mid = ceil(($low+$high)/2);
  $num = count($arr);
  while($low<=$high && $num--){
    if($a==$arr[$mid]){
      echo "查找的数的位置是第"."$mid";
      break;
    }
    list($low, $high) = $a > $arr[$mid] ? array($mid, $high) : array($low, $mid);
    $mid = ceil(($low+$high)/2);
  }
}

------解决方案--------------------
  相关解决方案