十分好用的二分查找模板 手撕二分还怕吗?

2019-10-31 星期四 开始吧#

十分好用的二分查找模板 手撕二分还怕吗?

最近发现一个二分查找很好用的模板,花了一点时间理解了下这个模板,然后这两天就会一直去找二分查找的题,利用那套模板来实现。这套模板和传统模板的不同在于传统的模板,可能我们会这样写:


function binarySerach($data, $res)
{
        $left  = 0;
        $right = count($data) - 1;
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1);
            if ($data[$middle] == $res) return $middle;
            else if ($data[$middle] > $res) $right = $middle - 1;
            else $left = $middle + 1;
        }
        return -1;
 }

这样写的缺点在哪呢,有两个点,一个是 while 里面产生了三个分支,其实大部分情况下,我们应该只需要去区分一下是否需要排除掉中位数,至于结果的处理,应该留到最后具体的场景实现。第二点就是 (这里看不出来,不过我可以举个场景),比如结果不存在,那么返回第一个大于或者第一个小于这类的场景。这时候因为你 while 的条件是小于或者等于,最后如果没有符合条件,需要格外返回别的数据以满足题目需求,这时候你必然要根据当前的语境去判断是返回 left 还是 right, 可能有些时候还会把自己绕晕,如果场景复杂的话。

下面我们来稍微改进一下当前模板来做下一道题目。

十分好用的二分查找模板 手撕二分还怕吗?

题目描述#

题目让我们找出重复的数,给定的数组的值都在 1-n 之间,数组总数是 n+1, 那么必然有数字是重复的,让我们来找出这个重复的数。

题目分析#

这道题可以有更好的解法 (我这里强行把它当做二分的场景),二分的解题思路就是取 n 的中位数,遍历数组,统计不大于中位数的个数,如果不大于中位数的个数比中位数还大,说明重复的数在中位数的左边 (注意包括中位数自己,理解一下这一句),否则的话重复的数肯定出现在中位数的右边,而且肯定不包括中位数。好了下面看代码再细讲。

代码实现#

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findDuplicate($nums) {
        $left = 1;
        $right = count($nums) - 1;
        while ($left < $right) {  // <
            $middle = ($left + $right) >> 1;
            $sum = 0;
            for ($j = 0; $j < count($nums); $j++) {
                if ($nums[$j] <= $middle) {
                    $sum++;
                }
            }
            if ($sum <= $middle) {  //排除掉中位数
                $left = $middle + 1;
            } else {   //不能排除中位数
                 $right = $middle;
            }
        }
        //相返回left还是right都可以  因为必然存在left==right
        return $left;
    }

这个模板第一步就是解除歧义,所有的判断都是 left<right, 这样最终肯定存在 left==right 不用再去进一步根据题意取哪边,语句中只剩下两个分支 (请忽略掉其他的逻辑来看), 一个往左边收,一个往右边收,至于结果,如果不存在其他的题意 随便返回 left 或者 right,有些题目是会变的,那么具体也在最后循环体外自行处理。接着中位数问题,每一次的判断往哪边靠,最大的争议点在于中位数是否要排除,必然会存在满足或者不满足,如果一方排除了中位数,那边另一方必然不能再排除,否则结果必错。这里还有一个地方很重要也值得你去思考的一个点。

     // $middle=floor(($l+$r)/2);
    // $middle=$l+floor(($r-$l)/2);
   // $middle=$l+(($r-$l)>>1); 
   // $middle = ($l + $r) >> 1;
  //上面的结果都是一样的,只是在数值大的情况下值会溢出

[1,3,6,9,12]  奇数的时候中位数没有争议直接是6 (0+4)/2 位置2=6
[1,3,6,9] 如果是($l + $r) >> 1  最终取的是左中位3  也就是位置1
[1,3,6,9] 想要右中位那么($l + $r + 1) >> 16

取左中位还是右中位重要吗?很重要!!!!稍不留神,你的程序就是死的。这里有个窍门就是如果你选择的是左中位数,那么在左边界语句缩边的同时一定要把中位数排除,为什么,道理很简单

  [1,3,6,9] 
  就像现在这样
  // $middle = ($l + $r) >> 1; 此时中位数是3
if(排除中位数的语句){
   $right = $miidle+1
}else{
   $left=$middle;
}
 //这时候对于如果走进的是else,就是灾难,因为left并不收缩,
 //这时候就进入了死循

所以你可以看到上面解题,我选择的是左中位数,我的左边界语句可以排除左中位数,就没问题。所以如果中位数选择的是左中位数,并且程序的左边界并不能排除中位数,那么这时候就应该选择右中位数,反之也是同样的道理。为了不吹牛,我拿出一个选右中位数的例子。为了省事直接拿的 Leetcode china 上的。

十分好用的二分查找模板 手撕二分还怕吗?

这道题二分查找按照上面规则的解。

  /**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x)
   {
        $left  = 0;
        $right = $x;
        while ($left < $right) {
            $middle = ($left + $right + 1) >> 1;
            //      $middle=($left+$right)>>1;
            if ($middle * $middle > $x) {
                $right = $middle - 1;
            } else {
                $left = $middle;
            }
        }
        return $left;
    }

注意看这里我选择了右中位数。下面我们来解释一下如果选择左中位数会咋么样。道理解释起来也很简单,按照题目的意思,一个数的平方大于目标数,那么它一定不会是目标数的平方根 (此时右边界语句一定能排除掉中位数!),反之,如果一个数的平方小于等于目标数,那么平方根可能就是中位数 (并不能把左中位数排除),左边界语句不能排除中位数,那么此时程序必要进入死循环,所以这时候我们需要取右中位数。

所以什么时候知道取哪边呢,也很简单,你可以先随便取左或者右,在收缩边界的时候,第一个语句直接写能排除中位数的,那么另一个边界一定不能排除中位数。然后再去判断取的那边中位数在边界的条件下是否能收缩空间,如若不能,反向获取中位数。当然这里的二分场景并不是很复杂,到了更复杂的二分场景,可能还需要做更多的操作。

最后再来一道#

十分好用的二分查找模板 手撕二分还怕吗?

这道题稍微加了一点游戏难度,当然我可没说用暴力破解法,也不说解题思路了,直接贴按照上面说的模板解题代码

  /**
     * @param Integer[][] $matrix
     * @param Integer $target
     * @return Boolean
     */
    function searchMatrix($matrix, $target)
    {
        $m = count($matrix);
        if ($m == 0) return false;
        $n = count($matrix[0]);
        if ($n == 0) return false;
        $left = 0;
        $right = $m * $n - 1;
        while ($left < $right) {
            $middle = ($left + $right) >> 1;
            $res = $matrix[$middle / $n][$middle % $n];
            if ($res < $target) {
                $left = $middle + 1;
            } else {
                $right = $middle;
            }

        }
        return $matrix[$left / $n][$left % $n] == $target ? true : false;
    }

最后附上这个二分查找思路的地址值得一看: 十分好用的二分查找模板

结语#

本人使用 php 开刷 Leetcode 之路,欢迎 PR:Leetcode-php

本作品采用《CC 协议》,转载必须注明作者和本文链接
吴亲库里
附言 1  ·  5年前

生时何必久睡 死后自然长眠

《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
未填写
文章
46
粉丝
119
喜欢
493
收藏
606
排名:176
访问:5.5 万
私信
所有博文
社区赞助商