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

解题思路：

有序的序列进行查找，优先想到二分查找，那先复习一下二分查找：

二分查找的条件：

1. 查找的内容在逻辑上来说是有序的；
2. 查找的数量只能是一个。

二分查找的过程：

1. 首先确定查找元素的中间的位置mid=(left+right)/2；
2. 如果中间的元素与要查找的元素target相同，说明找到了，返回中间元素的坐标；
3. 如果中间元素的值小于要查找元素的值，因为有序，所以target在中间元素的左边是不可能，target只可能在中间元素的右边，所以将查找范围缩小到[mid+1,right];
4. 如果中间元素的值大于要查找元素的值，target只可能出现在中间元素的左边，所以将查找范围缩小到[left,mid-1];
5. 重复上述过程，直到left的值大于right的值，如果没有找到，返回-1。

二分查找的时间复杂度：O(logn)

二分查找的空间复杂度:O(1)

二分查找代码如下，基于C++实现的：

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

对于该题目有一个旋转的限制条件，那就考虑修改二分查找。

1. 分别用两个指针left和right指向数组的第一个元素和最后一个元素，按照题目中旋转的规则，第一个元素的值应该大于或者等于最后一个元素的值，如果第一个元素的值小于最后一个元素的值，那么原数组是没有进行反转的递增数列，直接返回数组的第一个元素即可。
2. 接着我们和二分查找一样找到中间位置mid的元素，如果中间元素位于前面递增的子数组，那最小值将存在于[mid,right]之间，我们考虑将left的位置移到mid的位置，这样[left,right]又是一个旋转的数组；同样，当中间元素位于后边的递增序列，那最小值将存在于[left,mid]之间，考虑将right的位置移动到mid的位置，[left,right]又是一个旋转区间。
3. 重复上边的操作，最后我们会得到只有两个元素的[left,right]区间，right位置对应的的元素即为最小值。
4. 特殊情况，当序列为[5,1,2,5,5,5,5,5,5]这种特殊类型时，在判断left,right,mid时，三者相等，就无法使用二分查找进行移动，我们可以考虑使用顺序查找的方法。

时间复杂度：最坏的时候是对应的特殊情况为O(n)，平均就是二分查找的时间复杂度O(logn)；

空间复杂度：O(1);

代码是基于C++实现的：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0, right = rotateArray.size()-1;
        //mid初值为left，当序列没有进行旋转时，直接返回left
        int mid = left;
        while(left <= right && rotateArray[left] >= rotateArray[right]){
            //循环结束的条件，只剩两个元素
            if(right - left == 1){
                mid = right;
                break;
            }
            mid = (left + right)/2;
            //注意不要写成rotateArray[left] == rotateArray[right] == rotateArray[mid]，这样是错误的
            if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){
                return minInOrder(rotateArray, left, right);
            }
            if(rotateArray[mid] >= rotateArray[left]){
                left = mid;
            }else if(rotateArray[mid] <= rotateArray[right]){
                right = mid;
            }
        }
        return rotateArray[mid];
    }
    int minInOrder(vector<int> rotateArray, int left, int right){
        int result = rotateArray[left];
        for(int i=left+1; i<=right; i++){
            if(result > rotateArray[i]){
                result = rotateArray[i];
            }
        }
        return result;
    }
};