:算法之排序二分查找

php-leetcode之路 Leetcode-php

✏️二分查找

​

二分查找是一种常见的查找方式。在生活中有一个猜大小的例子。比如给定一个0-100的范围，让你猜出事先我所设置的数字，每次把数字的范围缩小到一半。第一次猜50，大了还是小了，继续缩小数字的范围。但是有一个前提，我们得保证我们查找的是一个有序的范围。

---

✏️查找思想

二分查找针对的是一个有序的集合。它的查找算法有点类型分治的思想，就像上面所说的。每次我通过中间的数和指定的数进行比较，判断大小，缩小猜测的区间，最多到区间等于0的时候，结果也就是最终指定的答案。二分查找是一种高效的查找算法，它的时间复杂度是O(logn).

---

✏️php实现二分查找

1.我们先实现一个最基础的，在一个有序数组中(数组没有重复的值)查找给定值。(迭代)

function binarySerach($data,$res)
{
    $l=0;
    $r=count($data)-1;
    while($l<=$r){
       // $middle=floor(($l+$r)/2);
       // $middle=$l+floor(($r-$l)/2);
        $middle=$l+(($r-$l)>>1); //使用位运算查找更高效
        if($data[$middle]==$res) return $middle;
        elseif ($data[$middle]>$res) $r=$middle-1;
        else $l=$middle+1;
    }
    return -1;
}
$data=[2,5,6,7,12,34];
$res=12;
var_dump(binarySerach($data,$res));

---

使用递归实现刚才的操作。

function binarySerach($data,$res){
    return recursion($data,0,count($data)-1,$res);
}

function recursion($data,$l,$r,$res)
{
    if($l>$r){
        return -1;
    }
    $middle=$l+(($r-$l)>>1);
    if($data[$middle]==$res) return $middle;
    elseif ($data[$middle]>$res) return recursion($data,$l,$middle-1,$res);
    else   return recursion($data,$middle+1,$r,$res);
}
$data=[2,5,6,7,12,34];
$res=12;
var_dump(binarySerach($data,$res));

---

✏️二分查找的变形问题

上面的那个注释是在数字没有重复的情况下，现在我们来实现数组中有重复值的情况下，如何查找出第一个等于给定值的元素。其实就是在做等于判断的时候如果索引是0那么是第一个等于给定值的数，或者当前等于给定值的上一个索引值不等于给定值。

function binarySerach($data,$res){
    $l=0;
    $r=count($data);
    while($l<=$r){
        $middle=$l+(($r-$l)>>1);
        if($data[$middle]>$res)  $r=$middle-1;
        elseif($data[$middle]<$res) $l=$middle+1;
        else{
            if($middle==0 || $data[$middle-1] !==$res) return $middle;
            else $r=$middle-1;
        }
    }
}
$data=[2,5,6,7,8,8,10];
$res=8;
var_dump(binarySerach($data,$res));

---

查找第一个大于等于给定值的元素。

//查找第一个大于等于给定值的数
function binarySerach($data,$res)
{
    $l=0;
    $r=count($data)-1;
    while($l<=$r){
        $middle=$l+(($r-$l)>>1);
        if($data[$middle]<$res) $l=$middle+1;
        else{
            if($middle==0 || $data[$middle-1]<$res ) return $middle;
            else $r=$middle-1;
        }
    }

}
$data=[2,5,6,7,8,8,10];
$res=9;
var_dump(binarySerach($data,$res));

---

针对数组是一个循环有序的数组Leetcode35题

function binarySerach($data,$res)
{
    $l=0;
    $r=count($data)-1;
    while($l<=$r){
        $middle=$l+(($r-$l)>>1);
        if($data[$middle]==$res) return $middle;
        elseif ($data[$middle]>$data[$r]){
            if($data[$l]<=$res && $data[$middle]>$res) $r=$middle-1;
            else $l=$middle+1;
        }else{
            if($data[$middle]<=$res && $data[$r] >$res) $r=$middle-1;
            else $l=$middle+1;
        }
    }
}
$data=[5,6,7,8,1,2,3,4];
$res=7;
var_dump(binarySerach($data,$res));

当然二分查找还有很多的应用场景,我就总结到这了。

联系

​