题目

题解

这题与33题类似，33是查找，这一题是找最小值，也要利用旋转数组的性质

  • 如果中间的数小于等于最右边的数，则右半段是有序的,最小值在左半段（包括中间值）；
  • 若中间数大于最右边数，则左半段是有序的，最小值在右半段
    这时因为旋转之后最小值是一个分水岭，其所在位置是一个低谷。那么有序的那半段肯定没有低谷（除非低谷在中间，这个包含在情况一）
0　　1　　2　　 4　　5　　6　　7

7　　0　　1　　 2　　4　　5　　6

6　　7　　0　　 1　　2　　4　　5

5　　6　　7　　 0　　1　　2　　4

4　　5　　6　　 7　　0　　1　　2

2　　4　　5　　 6　　7　　0　　1

1　　2　　4　 　5　　6　　7　　0
  • 时间复杂度$O(logN)$
  • 空间复杂度$O(1)$
class Solution {
public:
    int findMin(vector<int>& nums) {//与#33类似，也是二分法
        int left = 0,right = nums.size()-1;
        while(left<right){//设置循环
            int mid = left + (right-left)/2;//寻找中间值
            if(nums[mid]<=nums[right]) right = mid;
            //如果中间的数小于等于最右边的数，最小值在左半段（包括中间值）；
            else left = mid+1;
            //如果中间的数小于等于最右边的数，最小值在右半段（不包括中间值）；
        }
        return nums[right];//注意这里要返回右指针的，因为情况一包括了最小值在中间的情况，用右指针可以选到中间。
    }
};
```cpp