153.md

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

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

---

:pencil2:描述

给定一个不知道在哪个点发生旋转的有序升序数组，求数组中最小值。

---

:pencil2:题目实例

​

:pencil2:题目分析

这道题做个类似的，也是在哪个点发生旋转，求一个数，想不起来了，可以去看之前有关二分查找的题目，他并不是让你直接使用内置函数，或者自己写遍历，这样时间复杂度都是O(n)，应该通过二分查找来确定最小值所在的区间范围。

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

---

联系

​