LeetCode | Find Minimum in Rotated Sorted Array

本文主要是介绍LeetCode | Find Minimum in Rotated Sorted Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

这道题显然O(N)的解法是可解的，但是既然数组是有序的，其实可以采用O(lgN)复杂度内解决。

有一个十分十分重要的性质是：
a[left] < a[right]的时候，a[left]为最小值。

例如对于：
6 7 0 1 2 3 4 5
第一轮：left=0,right=7;mid=3,a[mid]=1;
a[left]>a[mid] right=mid=3;
第二轮：left=0,right=3,mid=1,a[mid]=7
a[left]< a[mid],left=mid+1=2;return 0;正确；

这是因为在a[left]>=a[right]的时候，必然会引起区间的收缩，且会向接近最大、最小值的方向收缩；
因为收缩的策略是a[left]>=a[right],这时候表示左侧有部分数据是被rotate过的，于是判断a[left]<=a[mid]否。
如果是，则最小值位于mid~right内，故left=mid+1;

本身二分没有太大难度，但是这个重要的性质还是值得好好体会。

class Solution {
public:int findMin(vector<int>& nums) {int n=nums.size();int left=0,right=n-1;while(left<right){//非常重要的性质if(nums[left]<nums[right]) return nums[left];int mid=(left+right)/2;if(nums[left]<=nums[mid])left=mid+1;else right=mid;}return nums[left];}
};

这篇关于LeetCode | Find Minimum in Rotated Sorted Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---