輸出一個為遞增排序數(shù)組的旋轉(zhuǎn)數(shù)組中的最小元素——8

    把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3，4，5，1，2}為數(shù)組{1, 2，3, 4, 5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。

    當(dāng)然了，將數(shù)組遍歷一遍肯定能找出最小值，但其時間復(fù)雜度為O(N)，效率是最低的，因此，應(yīng)該有一種更高效的解決辦法。

    因為原數(shù)組是遞增的，因此數(shù)組的第一個元素一定是最小值，而旋轉(zhuǎn)之后，其最小值就會成為旋轉(zhuǎn)的分界點，因此，查找一個旋轉(zhuǎn)之后數(shù)組的最小值可以變成查找一個旋轉(zhuǎn)數(shù)組的旋轉(zhuǎn)點。而我們?nèi)匀豢梢园l(fā)現(xiàn)，在旋轉(zhuǎn)點之前的序列是遞增有序的，而在旋轉(zhuǎn)點之后的序列也是遞增有序的，因此可以這樣判斷：

1. 取數(shù)組的中間值；

2. 如果中間值比最左值大且比最右值小，那么這個數(shù)組就是遞增數(shù)組旋轉(zhuǎn)幅度為0，最小值就為數(shù)組第一個值，直接返回；

3. 如果中間值比左邊一個數(shù)小且比右邊一個數(shù)小，那么中間值就為旋轉(zhuǎn)點也就是最小值，直接返回；
   

4. 如果中間值比最左值大且比最右值大，那么中間值往左一定是遞增有序的，而旋轉(zhuǎn)點一定在中間值往右，將范圍縮到中間值右半邊重新從第1步開始；

5. 如果中間值比最左值小且比最右值小，那么中間值往右一定是遞增有序的，而旋轉(zhuǎn)點一定在中間值往左，將范圍縮到中間值左半邊重新從第1步開始；

    上面的分析其實是相當(dāng)于在用二分查找來做，這樣就將時間復(fù)雜度降為了O(lgN),下面用代碼來實現(xiàn)：

#include <iostream>
#include <assert.h>
using namespace std;

int find_min_num(const int *arr, size_t n)
{
    assert(arr && n); 

    int left = 0;
    int right = n-1;
    int mid = (right-left)/2;

    while(left < right)
    {   
        if((arr[left] <= arr[mid]) && (arr[mid] <= arr[right]))
        {
            break;//當(dāng)數(shù)組區(qū)間為遞增時，最小值就為最左值
        }
        else if((arr[mid-1] > arr[mid]) && (arr[mid+1] > arr[mid]))
        {
            return arr[mid];//當(dāng)取到的中間值就為旋轉(zhuǎn)點時，最小值就為中間值
        }
        else if((arr[left] <= arr[mid]) && (arr[mid] >= arr[right]))
        {
            left = mid + 1;//當(dāng)中間值比左邊大且比右邊大時
        }
        else
        {
            right = mid - 1;//除去上面的三種情況就只剩一種了，那就是中間值比左線小且比右邊小
        }

        mid = (right-left)/2 + left;
    }   
    return arr[left];
}

int main()
{
    int arr[] = {8, 9, 2, 3, 4, 5, 6, 7};
    
    int ret = find_min_num(arr, sizeof(arr)/sizeof(arr[0]));
    cout<<"the min number is: "<<ret<<endl;
    return 0;
}

運行程序，輸出結(jié)果為2；

可以將數(shù)組設(shè)定為不同的情況來檢驗。

《完》