[binary_search]旋转数组的最小数字

题目：

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

思路：

这道题花费了好多时间，15：19--0：58，看起来如此简单的一道题花费的时间让我崩溃。遇到二分边界就是噩梦。
一开始思路不清晰摸索了一番发现即使这种旋转数组二分依然可以查找就是要分情况。后来发现不是二分，而是用二分直接找断点。查找的目标是mid的哪一边的两端不是严格正序就是一个中断，然后思路混乱花了好久才分出所有情况：

1.这里设计到分割的覆盖情况（说白了就是没分割好情况。。。）中断点在左边的情况和在右边的情况，则相应的另一边肯定是合法的，可能是严格升序也可能是不降序，所以一共有四种组合排除掉两边都是严格降序（不可能的），则一边严格一边不严格的情况，一定是属于间断点出现的情况（跟最开始的讨论重合了。。。），然后就剩下两边都不降的情况，其实就是mid/low/high三点相同。所以逻辑上就就三条通路，左边有间断，右边有间断和两边无法判断。
2.考虑两边无法判断的情况，可以一开始将两边重合的都消除，反正他们不会是结果（全相等除外，这里用下标控制不会全相等），但是首先两边都消除可能让任意一边都有可能越界（断点跑出low/high），（要么是一个不同的值要么越界），左边越界正好在最小值上，右边越界会越过最小值，所以在无法判断的时候就让左边移动。而且也不能在一开始只消除一次，一开始消除后之后的切割也可能切出三点相同的情况。所以得放在每一次更新low/high里面。

3.越界之后会发生什么。越界之后（只有左边会）如果不加控制那么会等同于三点相同的情况（跳过两边有断点的情况，哪边都不迭代，这个时候mid大于low小于high，就是那种不可能的情况）（不是二分查找，二分会往界外的断点逼近），然后左边移动，因此最终是high的节点。解决的方法是当他越界之后本身就可以退出了。。。
4.再来说说坑爹的边界。二分的时候要注意更新边界是mid+1，不加1会导致目标不在查找表里时，最终在缺失间隔处的两个节点上死循环。加了1同样会越界但是二分里越界没事，然后中止条件也是=或者low>high。这道题不加1同样会死循环，在断点左右，然后加了1就是上面的越界情况了。

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int low=0, high=rotateArray.size()-1, mid;
       while(low < high && rotateArray[low]>=rotateArray[high]){
           mid = (low + high)/2;
           if(rotateArray[low] > rotateArray[mid]){
               high = mid;
           }
           else if(rotateArray[mid] > rotateArray[high]){ //如果省区else是if选择形态的，则要更新mid
               low = mid + 1;//+1是为了可以迭代，两个方向的迭代都没有加1会陷入死循环（中断处卡在两个元素中间，同二分查找），而加了1的又会越界
               //在这里，越界组基本是导致两个迭代都失效（这里的左右下表迭代是中断点但并不是朝中断点的方向出发，而是有就出发没有<越界>就什么都不坐），同三点相等，于是左端会移动）
           }
           else {
               ++low;
           }
//1.若是low/high/mid都相同的情况，一开始是选择去除相同的首尾，且循环去除，且在一开始就去除，但问题是去除会使low/high跳动，
// low经过中断处是最小值，high经过中断越过了最小值，（即使通过越界直接判断结果，low越界结果就是low，high越界结果是high后一个不统一），所以只让low跳动就好了，即（]
//2.如果越界按照上面说的就是左端不断移动到low high相遇退出则结果错误（一开始消除三点相等只外面一次，于是越界后是上下标不更新死循环，但问题不在于三点相等，而在于越界！）
       }
       return rotateArray[low];
    }
};

int main() {
    Solution s;
    s.minNumberInRotateArray(vector<int>{4, 5, 6, 1, 2, 3});
    return 0;
}

我真是吃了si，一道题写一天