KT學算法（二）——循環有序數組查找指定元素

問題描述

一個循環有序的數組是形如：“12,16,18,20,41,100,1,4,6,9” 這樣的數組。

問題分析

對于循環有序數組，一種簡單的定義是：

循環有序數組是将一個有序數組切成兩段，并交換位置得到引用塊内容

比如現将1,4,6,9,12,16,18,20,41,100在9和12處切分，得到兩段:1,4,6,9和12,16,18,20,41,100，再交換這兩段的位置就得到了一開始的循環有序數組。

另一種比較嚴格的定義是：

對于一個循環有序數組{A1，A2，……An},存在一個i，滿足1 < i < n,使得{A1，A2，……Ai}和{Ai，Ai+1，……An}同為單調不減，或單調不增數組。且{A1，A2，……Ai}中的任意一個元素恒大與等于或恒小于等于{Ai，Ai+1，……An}中的任意一個元素。

算法設計

對于這樣一個具有一定單調性的數組，最容易想到的O（n）算法顯然不是最佳結果。考慮到有序數列的查找算法，通過二分法，可以實作O（log n）的時間複雜度，是以，我們嘗試修改二分法，來實作O（log n）的循環有序數組查找指定元素算法。

理論基礎

二分法的本質在于，每次隻需要搜尋一半的數列，而且很容易判定，是哪一半數列需要被搜素。

本例中，我們依然可以每次隻搜尋一半的數列，但是，對于選擇哪一半數列需要繼續被搜素，就不像傳統的二分法那樣顯然了。

但是循環有序數組具有兩個非常優良的性質：

1.将一個循環有序數組一分為二，一定得到一個有序數組和另一個循環有序數組

2.長度不超過2的循環有序數組其實就是有序數組。

關于以上兩點，我也沒有嚴格的數學證明，讀者可以以最初的循環有序數組為例，或重新舉例，自行驗證。

這兩點性質為循環有序數組的二分法查找提供了理論基礎：對于一個給定的待搜尋元素，現将原數組一分為二，因為循環有序數組比較難以通過代碼判定，我們隻需要判定，哪一個數組是有序數組，且是否需要在這個有序數組中進行搜尋即可。

解題思路

首先我們要判定這個數組，是增加型的還是減少型的。也即是說，如果用之前的定義一來判定，我們要先弄清楚這個循環有序數組的原數組是單調不減的還是單調不增的。

這一點并不難，隻要比較數組的第一個元素和最後一個元素即可。也就是說，如果A1 > An,那麼A一定是增加型的循環有序數組，如果A1 < An,那麼A一定是增加型的循環有序數組。A1 = An是非常麻煩的情況，可以通過比較A2 和 An-1得出結果，這裡我就沒有考慮。

一旦确定了循環有序數組是增加型的還是減少型的，就要開始判斷左邊一半和右邊一半哪一個是有序的。這裡以增加型的舉例，減少型的同理。

如果A[middle] >= A[begin]，那麼左邊一定是有序的。因為如果左邊是循環有序的，那麼最大值點一定出現在左側，且最大值點左側的數恒大于最大值點右側的數。這與A[middle] > A[begin]沖突。反之同理。

确定了有序的一側後，就要判斷是不是在這一側立面搜尋了。這個判斷非常簡單，隻要确定待搜尋的數的值是否在有序數列的兩個端點值之間即可。

最後通過循環，就可以類似二分法，找到待搜尋的數的位置。

代碼實作

int main(int argc, const char * argv[]) {
//    int a[] = {12,16,18,20,41,100,1,4,6,9};
    int a[] = {,,,,,,,,,};
    int target = ;
    int arrayLength = sizeof(a)/sizeof(a[]) - ;

    int index = getIndex(a,target,arrayLength);
    index == - ? printf("not found") : printf("index = %d",index);

    return ;
}

int getIndex(int a[],int target,int arrayLength){
    int beginPos = ;
    int endPos = arrayLength;
    if (a[beginPos] >= a[endPos]) {
        while (beginPos <= endPos) {
            int middlePos = beginPos + (endPos - beginPos)/;
            int middleValue = a[middlePos];

            //說明這是一個在增加的循環有序數組
            if (middleValue >= a[beginPos]) {
                //左側單調遞增
                if (target == a[middlePos]) {
                    return middlePos;
                }
                else if (target < a[middlePos] && target >= a[beginPos]){
                    //一定是在左側查找
                    endPos = middlePos - ;
                }
                else{
                    //在右側查找
                    beginPos = middlePos + ;
                }
            }
            else{
                //右側單調遞增，同理
                if (target == a[middlePos]) {
                    return middlePos;
                }
                else if (target > a[middlePos] && target <= a[endPos]){
                    //一定是在右側查找
                    beginPos = middlePos + ;
                }
                else{
                    //在左側查找
                    endPos = middlePos - ;
                }
            }
        }
        //沒找到元素
        return -;
    }
    else{
        while (beginPos <= endPos) {
            int middlePos = beginPos + (endPos - beginPos)/;
            int middleValue = a[middlePos];

            //說明這是一個在減少的循環有序數組
            if (middleValue >= a[beginPos]) {
                //右側單調遞減
                if (target == a[middlePos]) {
                    return middlePos;
                }
                else if (target < a[middlePos] && target >= a[endPos]){
                    //一定是在右側查找
                    beginPos = middlePos + ;
                }
                else{
                    //在右側查找
                    endPos = middlePos - ;
                }
            }
            else{
                //左側單調遞減，同理
                if (target == a[middlePos]) {
                    return middlePos;
                }
                else if (target <= a[beginPos] && target > a[middlePos]){
                    //一定是在左側查找
                    endPos = middlePos - ;
                }
                else{
                    //在左側查找
                    beginPos = middlePos + ;
                }
            }
        }
        //沒找到元素
        return -;
    }
}
           

寫在最後

對于出現A0 = An的情況，我們繼續判斷A1和An-1的大小。是以可以通過循環來實作，是以，在最壞情況下，這個算法依舊可能變為線性的算法。當然，如果已經規定了循環有序數組中不會出現相同的元素，那麼就簡單多了。

由于僅僅測試了幾個資料，不保證代碼100%正确，歡迎熱心的讀者測試以上代碼，并告訴我可能存在的bug。謝謝。