剑指offer-JZ6

C++
本题考查二分查找的知识；
题目首现给定一个升序数组，然后将前 个元素放置到后面，完成旋转。
这里简化为
1--[low1----mid------high] =====> [mid+1------high,low-------mid]；
因此，为了找到low,可以利用这种顺序信息来做。
【 1 】 【 3 】 【 2 】
[mid+1-------------high,low---------mid]
1 如果 low_p到mid_p有序，那么说明最小在右侧；
2 如果 mid_p到hig_p有序， 那么说明最小在左侧；
3 无论针对哪一个，无序， 那么说明最小在该段范围内；
----当low----high指向同一个数，那么就是最小。

还存在一种情况，即存在相同数,以上比较就失效了，为了防止错过，low++,逐渐查找。
--------一开始可以先检查是否有序，若有序，则直接输出。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.empty()){
            return 0;
        }
        int low=0, high = rotateArray.size()-1, mid = 0;
         while(low<high){
             // if array is sorted then th first is the mininmin
             if (rotateArray[low] < rotateArray[high]){
                 return rotateArray[low];
             }
             mid = (low+high) / 2;
             if( rotateArray[mid] > rotateArray[low]){
                 low=mid+1;
             }else if( rotateArray[mid] < rotateArray[high]){
                 high = mid;
             }else{
                 low++;
             }
         }
         return  rotateArray[low];
    }
};

最糟糕的时间排序是：
[a,a,a,a,a,a,a,a,a,a]