題目描述：把一個數(shù)組最開始的若干個元素移動到數(shù)組的末尾，稱之為一個數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。

成都創(chuàng)新互聯(lián)主要從事成都網(wǎng)站制作、網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)惠來,十載網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575

例如：數(shù)組 {3,4,5,1,2} 為{1,2,3,4,5} 的一個旋轉(zhuǎn)，該數(shù)組的最小元素為 1。

分析：

int Min(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        throw new std::exception("Invalid parameters");
 
    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2])
    {
        // 如果index1和index2指向相鄰的兩個數(shù)，
        // 則index1指向第一個遞增子數(shù)組的最后一個數(shù)字，
        // index2指向第二個子數(shù)組的第一個數(shù)字，也就是數(shù)組中的最小數(shù)字
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            break;
        }
 
        // 如果下標(biāo)為index1、index2和indexMid指向的三個數(shù)字相等，
        // 則只能順序查找
        
        indexMid = (index1 + index2) / 2;
        // 縮小查找范圍
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }
 
    return numbers[indexMid];
}

int Min(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        throw new std::exception("Invalid parameters");
 
    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2])
    {
        // 如果index1和index2指向相鄰的兩個數(shù)，
        // 則index1指向第一個遞增子數(shù)組的最后一個數(shù)字，
        // index2指向第二個子數(shù)組的第一個數(shù)字，也就是數(shù)組中的最小數(shù)字
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            break;
        }
 
        // 如果下標(biāo)為index1、index2和indexMid指向的三個數(shù)字相等，
        // 則只能順序查找
        indexMid = (index1 + index2) / 2;
        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
            return MinInOrder(numbers, index1, index2);

        // 縮小查找范圍
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }
 
    return numbers[indexMid];
}

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

本文題目：旋轉(zhuǎn)數(shù)組中的最小數(shù)字
文章URL：http://aaarwkj.com/article22/jjppjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、網(wǎng)站策劃、網(wǎng)站維護(hù)、商城網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)