153. Find Minimum in Rotated Sorted Array.md

153. Find Minimum in Rotated Sorted Array

思路

要求一个经过循环移位后的排序数组(无重复元素)中的最小值. 其实这题是33. Search in Rotated Sorted Array 的前半部分, 所以搞懂33题了这题肯定完全没问题.

由于数组(移位前)是有序的所以肯定是二分, 设最小值在i处, 则数组A = nums[0,...,i-1]和B = nums[i,...,n-1]是分别递增的, 而且B的所有元素都小于A任意元素. 二分while循环中mid需要分三种情况:

1. 当nums[low] > nums[mid]时, 说明mid在B部分, 则i在区间[low, mid];
2. 否则即mid在A部分(B存不存在未知), 此时当nums[low] > nums[high]时, 说明B部分存在, 则i在区间[mid+1, high];
3. 否则, 即mid在A部分且B不存在, 即low到high是严格递增的, 最小值即nums[low], 直接返回即可.

或者考虑nums[high]和nums[mid]的大小关系（考虑nums[low]和nums[mid]关系不是一个好选择, 见33题解）也可以：

• 若nums[mid] < nums[high]，此时最小值只能是位于[low, mid]。
• 否则若nums[mid] > nums[high]，此时最小值只能是位于[mid+1, low]。
• 假设nums[mid] == nums[high]，此时low = mid = high，最小值就是nums[mid]。

注意边界情况.

C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0, high = nums.size() - 1, mid;
        
        while(low <= high){
            mid = low + (high - low) / 2;
            if(nums[low] > nums[mid]) high = mid;
            else if(nums[low] > nums[high]) low = mid + 1;
            else return nums[low];
            // 或者:
            // if(nums[mid] > nums[high]) low = 1 + mid;
            // else if(nums[mid] < nums[high]) high = mid;
            // else return nums[low];
        }
        return nums[low]; // 这一步应该是不会执行的
    }
};