旋转数组的最小数字

问题描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解决方案

咋眼一看这题，很简单啊，就一次遍历找到最小值就可以了啊，那答案就很简单。如下给出一般解决方案

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {

        if(rotateArray.size()==0)
        {
            return 0;
        }
        for(size_t i=0;i<rotateArray.size()-1;++i)
        {
            if(rotateArray[i] > rotateArray[i+1])
            {
                return rotateArray[i+1];
            }
        }
        return 0;
    }
        
}

做完这个题目时我们应该更加进一步去思考该题，这个题难道就这么简单？其实不然，当我们控制其时间复杂度时，我们可以思考另外一种方式来解决，如下给出思路：

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。
我们试着用二分查找法的思路在寻找这个最小的元素。
首先我们用两个指针，分别指向数组的第一个元素和最后一个元素。按照题目旋转的规则，第一个元素应该是大于或者等于最后一个元素的（这其实不完全对，还有特例。后面再讨论特例）。
接着我们得到处在数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。
我们可以把第一指针指向该中间元素，这样可以缩小寻找的范围。同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。
我们可以把第二个指针指向该中间元素，这样同样可以缩小寻找的范围。我们接着再用更新之后的两个指针，去得到和比较新的中间元素，循环下去。
按照上述的思路，我们的第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最后第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。
也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
  if(rotateArray.empty()) return 0;
        int begin = 0;
        int end = rotateArray.size()-1;
        int middle = 0;
        if(rotateArray[begin]<rotateArray[end])
        {
            return rotateArray[begin];
        }
        while(begin < end)
        {
            if(end - begin == 1){
                middle = end;
                break;
            }
                
            int middle = (begin + end )/2;
            if(rotateArray[middle] >= rotateArray[begin])
            {
                begin = middle;
            }
            else if(rotateArray[middle] <= rotateArray[begin]){
                end = middle;
            }
        }
       
        return rotateArray[middle];
    }
};