面试题11：旋转数组的最小数字（c++）【剑指offer】

下面代码也能通过，但是存在几个问题，如数列“1,2,3,4,5”和“1,1,1,0,1”则无法找到最小值。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()<=0) return 0;
        int length=rotateArray.size();
        int head=rotateArray[0];
        int low=0,high=length-1,mid;
        while(low<high){
            mid=(low+high)/2;
            if(rotateArray[mid]>=head) low=mid+1;
            if(rotateArray[mid]<head) high=mid;
        }
        return rotateArray[low];
    }
};

改进：

class Solution {
public:
    //参考《剑指offer》
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()<=0) return 0;
        int length=rotateArray.size();
        int low=0,high=length-1,mid=low;
        while(rotateArray[low]>=rotateArray[high]){
            if(high-low==1){ // low始终指向左边递增数组，high始终指向右边递增数组
                mid=high;    // 当“high-low=1”时，最小值就是rotateArray[high]
                break;
            }

            mid=(low+high)/2;

            //三个值相等时，只能进行顺序查找，找出最小值
            if(rotateArray[low]==rotateArray[mid]&&rotateArray[mid]==rotateArray[high]){
                return seqsearch(low,high,rotateArray);
            }

            if(rotateArray[mid]>=rotateArray[low]) low=mid;
            else if(rotateArray[mid]<=rotateArray[high]) high=mid;
        }
        return rotateArray[mid];
    }

    //顺序查找，找到最小值
    int seqsearch(int low,int high,vector<int> rotateArray){
        int a=rotateArray[low];
        for(int i=low+1;i<high;i++){
            if(rotateArray[i]<a) a=rotateArray[i];
        }
        return a;
    }
};