真正优秀的程序员是那些专注于认识、理解、沟通和解决问题的人,你得明白,软件只是用来增加效率的工具而已

php之二分查找算法

二分查找法整体原理

  • 1.采用折半的方法查找,首选用$low 表示最低位,$mix 表示中间位置 $high 表示最高位
  • 2.拿val 跟 $mix 比较,如果等于$mix 则直接返回,小于$mix 则$high = $mix -1;(往后移)
  • 3.如果大于$mix ,则$low 的值 向前移($low = $mix +1)。
  • 4.直到最后越界 –>如果$low > $high 则退出,证明查找失败。

1.二分查找法 递归的方法

  • 使用递归的条件,如果一个函数实现的方法跟其本身实现的方法步骤相同,则可以使用函数自己。
  • 递归的两个特点: 自调用 ,有明确的退出条件
function binarySearch($arr,$low,$heigh,$val)
{
    if($low <= $heigh){
      $mix = floor(($low+$heigh)/2); //中间值

     if($arr[$mix] == $val){
        return $mix;
     }

     if($val < $arr[$mix]){
       $heigh = $mix - 1;
       return binarySearch($arr,$low,$heigh,$val); //再次递归查找
     }

     if($val > $arr[$mix]){
        $low = $mix + 1;
        return binarySearch($arr,$low,$heigh,$val);
     }

    }else{
        return -1;
    }

}

$arr = [1,3,5,7,9,11,13,15,17];
print_r(binarySearch($arr,0,count($arr)-1,2)); //echo 2

2.二分查找之循环查找

function binarySearch2($arr,$val)
{
    $low    = 0;
    $high   = count($arr) -1;

    while($low <= $high){

        $mix = floor(($low+$high)/2);

        if($val == $arr[$mix]){
            return $mix;
        }

        if($val < $arr[$mix]){
            $high = $mix - 1;
        }

        if($val > $arr[$mix]){
            $low = $mix + 1;
        }
    }

    return -1;
}

$arr = [1,3,5,7,9,11,13,15,17];
print_r(binarySearch2($arr,9)); //echo 4
微风小站 » php之二分查找算法
分享到: 更多 (0)

相关推荐