剑指Offer算法题-旋转数组中的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

题解

这道题最简单的办法是顺序扫描一遍。一个最快的解决办法是用sort函数排序，然后返回arr[0]。一个更好的解决办法是二分法。数组前后两段式有序的，可以使用二分法来做

特别注意[1,1,1,1,1]这种形式。如果你的代码超时，可能是因为没处理好这种情况

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0) return 0;
        int iter1 = 0,
            iter2 = rotateArray.size() - 1, 
            mid = rotateArray.size() / 2;
        while(iter1 < iter2){
            //中间大于右侧，说明目标在右侧
            // 5 6 7 8 9 10 1 2 3 4
            if(rotateArray[mid] > rotateArray[iter2])
                iter1 = mid, mid = (iter1 + iter2) / 2;
            //中间小于右侧，说明目标在左侧
            // 8 9 10 1 2 3 4 5 6 7
            else if(rotateArray[mid] < rotateArray[iter2])
                iter2 = mid, mid = (iter1 + iter2) / 2;
            //左边最小，直接返回左边的
            // 1 2 3 4 5 6 7 8 9 10
            else if(rotateArray[iter1] < rotateArray[iter2])
                return rotateArray[iter1];
            //无法判断的情况，左指针移动一位，试探
            // 1 1 0 1 1 1 1 1 1 1
            // 1 1 1 1 1 1 1 1 0 1
            else
                iter1++, mid = (iter1 + iter2) / 2;
            //指针重合，则为最小值
            if(iter1 == iter2){
                return rotateArray[iter2];
            }
            //如果指针紧贴，则最小值为其中较小的一个 
            if(iter2 - iter1 == 1)
                return min(rotateArray[iter1], rotateArray[iter2]);
        }
        return 0;
    }
};