輸出一個(gè)為遞增排序數(shù)組的旋轉(zhuǎn)數(shù)組中的最小元素——8-創(chuàng)新互聯(lián)

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

創(chuàng)新互聯(lián)是專業(yè)的劍川網(wǎng)站建設(shè)公司，劍川接單;提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行劍川網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

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

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

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

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

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

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

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

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

            網(wǎng)頁名稱：輸出一個(gè)為遞增排序數(shù)組的旋轉(zhuǎn)數(shù)組中的最小元素——8-創(chuàng)新互聯(lián)            

            文章起源：http://www.jiaotiyi.com/article/hpide.html