81.md

✏️基础刷题之(81. Search in Rotated Sorted Array II)

. 2019-10-23 吴亲库里 库里的深夜食堂

✏️描述

假设已升序排序的数组在某个位置上发生了旋转,给定一个目标数,查找这个数是否存在数组中,这道题最大的不同在于可能数组中存在重复值.

---

✏️题目实例

​

---

✏️题目分析

这道题可以使用二分查找去解题,之前写过一个二分查找好用的模板文章,具体地址请移步 https://mp.weixin.qq.com/s?__biz=MzU3Mzc5NTU2MQ==&mid=2247484785&idx=1&sn=4daaf34c9714ff3388fc4a4ad4190728&chksm=fd3d78f7ca4af1e1be14c1c1ca9bd220a74512528e74caed853bf5eb7b3877837fabcb1411c0&token=889524492&lang=zh_CN#rd

这是第一版不存在重复值:https://github.com/wuqinqiang/leetcode-php/blob/master/0-50/33.md

只要中间数比最右边的还小，说明右边是有序的，一旦满足目标值大于等于中间数并且小于等于right值，说明目标可能在右边(并且包括中间数)，否则就在左边 并且肯定不包括中间数。反之也是同样的道理。最后再做下尾部处理即可。

✏️最终实现代码

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Boolean
     */
    function search($nums, $target) {
        $num=count($nums);
        if($nums==0) return false;
        $left=0;
        $right=$num-1;
        while($left<$right){
            $middle=($left+$right+1)>>1;
            if($nums[$middle]<$nums[$right]){  //右边的一定是顺序数组包括中位数
              if($nums[$middle]<=$target && $nums[$right]>=$target){
                    $left=$middle;
              }else{
                  $right=$middle-1;
              }
            }else if($nums[$middle]>$nums[$right]){ //左边数顺序 包括中位数
                if($nums[$left]<=$target && $target<$nums[$middle]){  
                    $right=$middle-1;
                }else{
                    $left=$middle;
                }
            }
            else{
                if($nums[$right]==$target) return true;
                $right--;
            }
        }
        
        return $nums[$left]==$target;
    }

---

联系

​