剑指Offer11 旋转数组的最小数字（C++）_剑指 offer 11. 旋转数组的最小数字 c++

其实很容易看出这是一道二分查找的题目，但是二分查找的背后还是有很多的坑

1、数组可以重复

2、我被坑了的地方，若干个元素旋转可以是0个元素！！也就是说数组可能压根没有旋转，就直接是递增的，这种这里其实就有一个坑，mid的值不能和left作比较，因为没有意义！！

[1,3,5]  此时num[mid]>num[left],但是数组的最小值在mid左边

[3,4,5,1,2] 同样num[mid]>num[left]，但是此时数组最小值在mid右边

但不同的是如果right值比mid的值大，那么右半部分肯定是递增的，所以可以以此作为切入点

那么right值和mid值相等时候又该怎么处理呢？

实际上这里是更加需要注意的地方，比如[2,2,2,1,2]，或者[2,1,2,2,2]这种情况下，num[right]=num[left],我们是无法判断最小值在mid左边或者右边，所以只能right--，二分法时间复杂度退化，最终算法如下：

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0,right = numbers.size()-1;
        while(left<right){
            int mid = left + (right-left)/2;
            cout<<left<<right<<mid<<endl;
            if(numbers[mid]>numbers[right]){
                left = mid+1;
            }
            else if(numbers[mid]<numbers[right]){
                right = mid;
            }
            else{
                right--;
            }
        }
        return numbers[left];
    }
};

这里其实还有一个值得注意的地方就是 为什么left要mid+1，然后right只能mid，因为当numbers[mid]<numbers[right]时说不定mid所在的位置就是最小值呢，所以right = mid