题解 | #旋转数组的最小数字#

题解一：暴力搜索
主要思路：从头遍历找寻最小值

复杂度分析：
时间复杂度：O(N)，遍历整个数组
空间复杂度：O(1)，只使用常数个临时变量
实现如下:

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0) return 0;
        int ans = INT_MAX;
        for(auto i : rotateArray)//C++11语法，遍历数组；
        {
            ans = min(i,ans);//比较最小；
        }
        return ans;
    }
};

题解二：二分查找
题解思路：利用数组是由非递减排序旋转来的
主要思路：
1.数组可以分为两个有序的子数组。其中，左排序的数组的值大于右排序数组中的值。
如图：

2.声明left,right 分别指向数组的左右两端；
3. mid = (left+right) / 2 为二分的中间位置。
4.mid，left,right分为三种情况：
a. rotateArray[mid] > rotateArray[right]时， 那么 最小值一定在 [mid+1,right]区间中；
b.rotateArray[mid] < rotateArray[right]时，那么最小值一定在[left,mid]区间内。
c. rotateArray[mid] = rotateArray[right]时，无法判断最小值在哪个区间，所以此时只能缩小right的值。
如图：

复杂度分析：
时间复杂度O(logN)，二分
空间复杂度:O(1)，只使用常数个临时变量
实现如下：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0, right = rotateArray.size()-1;
        while(left < right)
        {
            int mid = (left+right) / 2;//取中间值
            if(rotateArray[mid] > rotateArray[right])  left = mid+1;//搜索右边
            else if(rotateArray[mid] < rotateArray[right])  right = mid;//搜索左边
            else right -= 1;
        }
        return rotateArray[left];
    }
};