154.md

:pencil2:Leetcode基础刷题之(154. Find Minimum in Rotated Sorted Array II)

2019-07-18 吴亲库里 库里的深夜食堂

---

:pencil2:描述

给定一个不知道在哪个点发生旋转的有序升序数组，求数组中最小值。这题和上一题最大的区别就是有重复值。

---

:pencil2:题目实例

​

:pencil2:题目分析

还是需要通过中间点查找，不同的是每次二分查找如果等于中间数，那么直接把左边的向右边的移动一位，大于或者小于的情况，我们都可以求出这局部的最小值，然后缩小分区，最后进行求左中右三部分的最小值即整体最小值。

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findMin($nums) {
        $l=0;
        $r=count($nums)-1;
        $res=$nums[0];
        while($l<$r-1){
            $middle=$l+(($r-$l)>>1);
            if($nums[$l]<$nums[$middle]){
                $res=min($nums[$l],$res);
                $l=$middle+1;
            }elseif($nums[$l]>$nums[$middle]){
                $res=min($res,$nums[$r]);
                $r=$middle;
            }else ++$l;
        }
        $res=min($res,$nums[$l],$nums[$r]);
        return $res;
    }

---

联系

​