旋转数组的最小数字 -- C++

注意，本文仍然用的vector数组，但其实可以换用普通数组，效率会有所提升
C++：
先将vector的长度提取出来

n = Array.size()

对于题目中的特殊情况，我们O(1)特殊判断就行了

if(n==0)
    return 0;

然后分析题目：
对于“旋转”前的数，应该是递增的：

“旋转”一次后，应该是这样的：

我们可以直观感受到，这个数列是先由总起点上升到第一个终点，然后由第二个起点上升到最后终点，并且：
第一个终点 > 总起点 > 总终点 > 第二个起点

由此我们可以得到
方法1：暴力扫一遍，时间复杂度 O(n)

for(int i=1;i<=n;i++)
    if(Array[i] < Array[i-1])
        return Array[i];

方法2：二分搜索，时间复杂度 O(log(n))
设 left = 0 ，right = n-1
mid = (l+r)>>1;
如果 Array[mid-1] > Array[mid]
那么 Array[mid] 刚好为我们找的数,可以直接返回,
否则 Array[mid-1] < Array[mid] < Array[mid+1] 一定成立。
我们只需要看看 Array[mid] 是不是大于总起点就行了，如果大于总起点，那说明在左上升半段，否则在右上升半段。
以此缩小二分范围。
代码：

    int n=Array.size();
    if(n==0)
        return 0;
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(Array[mid-1]>Array[mid])
            return Array[mid];
        if(Array[mid]>=Array[0])
            l=mid+1;
        else
            r=mid;
    }
    return Array[l];