把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，成為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出數(shù)組的最小元素。

解析：這題最容易想到的就是順序搜索一遍，但是這樣子的時(shí)間復(fù)雜度在 O(n)。我們可以用類(lèi)似二分的思想來(lái)找到那個(gè)最小的元素，但是有一種特殊情況會(huì)讓我們必須使用順序查找，因?yàn)樵谶@個(gè)特殊情況下無(wú)法判斷是要往左半部分查找還是右半部分查找。

先想一下如何使用二分查找。我們把被旋轉(zhuǎn)到末尾的那個(gè)小的遞增片段計(jì)作 a，由于旋轉(zhuǎn)作用而向前挪動(dòng)了的剩下的那個(gè)遞增片段計(jì)作 b。例如，原有片段是 {1,2,3,4,5,6,7,8}，我把 {1,2,3} 旋轉(zhuǎn)到后面，那么旋轉(zhuǎn)后就變成了 {4,5,6,7,8,1,2,3}。這個(gè)時(shí)候，a={1,2,3}，b={4,5,6,7,8}。我們?cè)诙植檎业臅r(shí)候，中間位置上的數(shù)字有可能落在 a 里，也有可能落在 b 里。如果落在 a 里面，那么最小的數(shù)字應(yīng)該還在中間數(shù)字的左邊。如果落在 b 里，最小的數(shù)字應(yīng)該在中間數(shù)字的右邊。用這個(gè)思想我們就可以不斷的去逼近最小的數(shù)字。多寫(xiě)幾個(gè)例子，模擬一邊過(guò)程，你就會(huì)發(fā)現(xiàn)最后中間的數(shù)字指向的就是最小的數(shù)字。

我們考慮幾種特殊情況。首先，當(dāng)前比較的數(shù)組已經(jīng)遞增了。那么這個(gè)時(shí)候數(shù)組的第一位就是最小的數(shù)字，我們可以直接返回。我們可以把中間位的初始值設(shè)定為第一位，在每次進(jìn)入循環(huán)的時(shí)候檢查該數(shù)組是否已經(jīng)遞增。如果已經(jīng)遞增，就不需要進(jìn)入循環(huán)了，直接返回第一位就好。然后是我剛說(shuō)到的，無(wú)法使用二分查找的方法。考慮 {0,1,1,1,1}，旋轉(zhuǎn)前四位得到 {1,0,1,1,1}。開(kāi)頭、中間和結(jié)尾的位置都是1，那這個(gè)時(shí)候就無(wú)法判斷要往左邊走還是往右邊走了。如果遇到了這個(gè)情況，那么只能順序搜索當(dāng)前序列，找到最小的元素。

答案：

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];
}