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

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

  因為原數組是遞增的，因此數組的第一個元素一定是最小值，而旋轉之后，其最小值就會成為旋轉的分界點，因此，查找一個旋轉之后數組的最小值可以變成查找一個旋轉數組的旋轉點。而我們仍然可以發(fā)現(xiàn)，在旋轉點之前的序列是遞增有序的，而在旋轉點之后的序列也是遞增有序的，因此可以這樣判斷：

1. 取數組的中間值；

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

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

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

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

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

#include 
#include 
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;//當數組區(qū)間為遞增時，最小值就為最左值
        }
        else if((arr[mid-1] > arr[mid]) && (arr[mid+1] > arr[mid]))
        {
            return arr[mid];//當取到的中間值就為旋轉點時，最小值就為中間值
        }
        else if((arr[left] <= arr[mid]) && (arr[mid] >= arr[right]))
        {
            left = mid + 1;//當中間值比左邊大且比右邊大時
        }
        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: "<
運行程序，輸出結果為2；
可以將數組設定為不同的情況來檢驗。
《完》
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。
            

            新聞標題：輸出一個為遞增排序數組的旋轉數組中的最小元素——8-創(chuàng)新互聯(lián)            

            網頁地址：http://weahome.cn/article/hpide.html