寻找旋转数组中的极小值 - leetcode

此类问题，不管是求最大值还是最小值，都是二分问题中的经典问题。对于这类问题晚上也都有很多经典的解析，但大多数都忽略了一个最重要的问题：到底是选取nums[0]还是nums.back()作为参考点，以及为什么？

我翻阅了一些解析，就拿上面所列出的这道题，很多答案直接就说：拿nums.back()做参考点，只要nums[mid]>nums.back()，那么最小值就肯定在nums[mid]的右边（开区间）；反之，只要nums[mid]<nums.back()，那么最小值肯定在nums[mid]的左边（闭区间）；

那么问题来了，我拿nums[0]做参考点不是照样满足条件吗？然后用nums[0]去做题，ok，马上就错了，举个case：[2,0,2,2,2,2,2]，最后就得不到正确答案；

原因出在哪里？其实不难想，就是当nums数组本身就没有旋转的时候，此时nums[left]就已经是最小值了，但是由于先前是拿nums[left]做参考点，所以反而会跳过这个最小值；

拿nums.back()做参考点就一定不会出现这个问题吗？其实不然，只要题目换成了去找最大值，照样要出问题。所以很多题解都是写的半懂不懂，很多道理都没有说清楚。

总结一下，其实找哪个参考点，是左边还是右边，都无所谓，关键是针对特殊case去做一些特殊处理。

下面是找出这个问题之后，以nums[0]为参考点的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        int left = 0, right = len-1;
        int ans = INT_MAX;
        while(left < right){
            int mid = left + (right-left) / 2;
            if(nums[mid] == nums[left]){
                ans = min(ans, nums[left++]);
                continue;
            }
            if(nums[mid] > nums[left]){
                ans = min(ans, nums[left]); // 重点就在这里
                left = mid + 1;
            } else {
               right = mid;
            }
        }
        return min(ans, nums[left]);
    }
};