把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾瘤旨，成為數(shù)組的旋轉。輸入一個遞增排序的數(shù)組的一個旋轉营勤，輸出數(shù)組的最小元素富弦。

解析：這題最容易想到的就是順序搜索一遍沟娱，但是這樣子的時間復雜度在 O(n)。我們可以用類似二分的思想來找到那個最小的元素腕柜，但是有一種特殊情況會讓我們必須使用順序查找济似，因為在這個特殊情況下無法判斷是要往左半部分查找還是右半部分查找。

先想一下如何使用二分查找盏缤。我們把被旋轉到末尾的那個小的遞增片段計作 a碱屁，由于旋轉作用而向前挪動了的剩下的那個遞增片段計作 b。例如蛾找，原有片段是 {1,2,3,4,5,6,7,8}娩脾，我把 {1,2,3} 旋轉到后面，那么旋轉后就變成了 {4,5,6,7,8,1,2,3}打毛。這個時候柿赊，a={1,2,3}，b={4,5,6,7,8}幻枉。我們在二分查找的時候碰声，中間位置上的數(shù)字有可能落在 a 里，也有可能落在 b 里熬甫。如果落在 a 里面胰挑，那么最小的數(shù)字應該還在中間數(shù)字的左邊。如果落在 b 里椿肩，最小的數(shù)字應該在中間數(shù)字的右邊瞻颂。用這個思想我們就可以不斷的去逼近最小的數(shù)字。多寫幾個例子郑象，模擬一邊過程贡这，你就會發(fā)現(xiàn)最后中間的數(shù)字指向的就是最小的數(shù)字。

我們考慮幾種特殊情況厂榛。首先盖矫，當前比較的數(shù)組已經(jīng)遞增了宇驾。那么這個時候數(shù)組的第一位就是最小的數(shù)字兰迫，我們可以直接返回渔呵。我們可以把中間位的初始值設定為第一位馏段，在每次進入循環(huán)的時候檢查該數(shù)組是否已經(jīng)遞增。如果已經(jīng)遞增湃望，就不需要進入循環(huán)了拷橘，直接返回第一位就好。然后是我剛說到的喜爷，無法使用二分查找的方法√汛剑考慮 {0,1,1,1,1}檩帐，旋轉前四位得到 {1,0,1,1,1}。開頭另萤、中間和結尾的位置都是1湃密，那這個時候就無法判斷要往左邊走還是往右邊走了。如果遇到了這個情況四敞，那么只能順序搜索當前序列泛源，找到最小的元素。

答案：

int MinInOrder(int* numbers, int index1, int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i)
    {
        if(result > numbers[i])
            result = numbers[i];
    }

    return result;
}

int Min(int* numbers, int length)
{
    if(numbers == nullptr || length <= 0)
        throw exception();

    int first = 0, last = length-1;
    int mid = first; //將中間位初始為第一位
    while (numbers[first]>=numbers[last]) //如果該序列本身就是遞增序列忿危，退出 while
    {
        if (last-first == 1)
        {
            mid = last;
            break;
        }
        else
        {
            mid = first + ((last-first)>>1);
            if (numbers[first]==numbers[mid] && numbers[mid]==numbers[last])
                return MinInOrder(numbers, first, last);
            else
            {
                if (numbers[mid]>=numbers[first])
                    first = mid;
                else if (numbers[mid]<=numbers[first])
                    last = mid;
            }
        }
    }
    return numbers[mid];
}