（LeetCode 153）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.

题目：

给定一旋转有序数组，求该数组的最小值。

思路：

• 二分查找Binary Search
• 比较简单，不详述，主要在于二分查找过程的循环不变量的判断
• 递归思想
• 旋转有序数组的循环不变量：
• 旋转数组的最后一个值一定小于第一个值（无旋转情况例外）。在二分循环时，对于区间的判断很重要。
• 以最右值为pivot，当num[mid]>num[right]，为了维持旋转不变量，即数组的第一个值大于最后一个值，应当将left=mid，这样依旧num[left]>num[right]。当num[mid]<num[right]，应当将right=mid，这样对于无旋转的数组同样适用，因为num[mid]肯定小于num[right]，数组不断地往左收缩，最终会到num[0]。
• 以最左值为pivot，同样可以通过二分求旋转数组的最小值，但对于无旋转数组而言，num[mid]肯定大于num[left]，数组会不断地往右收缩，最终会到num[len-1].
• 所以，要么采用最右值来收缩二分查找区间，要么将无旋转数组单独考虑。
• 最小值小于左右两边的值，满足其一即可。
• if(nums[mid]<nums[mid-1])  return nums[mid];
• if(nums[mid]>nums[mid+1])  return nums[mid+1];
• 因为数组是从0下标开始的，因此最好通过第二种情况来判断。
• 方法总结：
• 单独考虑无旋转数组，即一开始就判断num[0]<num[len-1]？如果是，则返回num[0]。再考虑旋转数组，通过最左值或者最右值来收缩二分查找的区间。对于最小值的判断，采用if(nums[mid]>nums[mid+1])  return nums[mid+1]；如果出现无旋转数组，单独考虑无旋转数组的话，时间效率更高。
• 不单独考虑无旋转数组，则通过最右值来收缩二分查找的区间。对于最小值的判断，采用if(nums[mid]>nums[mid+1])  return nums[mid+1];

代码：

1、非递归

class Solution {
public:
    int findMin(vector<int>& nums) {
        int len=nums.size();
        int left=0;
        int right=len-1;
        int mid;
        
//        if(nums[left]<nums[right])
//            return nums[left];
            
        while(left<=right){
            if(left==right)
                return nums[left];
            mid=(left+right)/2;
//            if(nums[mid]<nums[mid-1])
//                return nums[mid];
            if(nums[mid]>nums[mid+1])
                return nums[mid+1];
            if(nums[mid]>nums[right])
                left=mid;
            if(nums[mid]<nums[right])
                right=mid;
        }
    }
};

2、递归

class Solution {
    public:
        int findMin(vector<int> &num) {
            int left = 0, right = num.size() - 1;
            return BinarySearch(num, left, right);
        }
        
    private:
        int BinarySearch(vector<int> &num, int left, int right) {
            if(left==right) return num[left];
            int mid = (left + right) / 2;
//            if(num[mid] < num[mid - 1]) return num[mid];
            if(num[mid] > num[mid + 1]) return num[mid + 1];
            if(num[mid] < num[right]) return BinarySearch(num, left, mid);
            if(num[mid] > num[right]) return BinarySearch(num, mid, right);
        }
};