[解決済み] ソートされ回転した配列内の検索

質問

面接の準備をしているときに、こんな面白い質問を受けました。

あなたは、並べ替えられた後、回転させられた配列を与えられました。

例えば

• Let arr = [1,2,3,4,5] であり、ソートされている
• 右に2回回転させると [4,5,1,2,3] .

さて、この並べ替え＋回転した配列の中で、どのように検索するのがベストでしょうか？

配列の回転を解除して、2値探索を行うことができます。しかし、これは入力配列の線形探索と同じで、最悪の場合、O(N)になります。

何かポイントを教えてください。このための特別なアルゴリズムについていろいろググってみたのですが、見つかりませんでした。

CとC++は理解できます。

どのように解決するのですか？

これは O(logN) を少し修正したバイナリサーチを使用します。

ソート＋回転配列の面白いところは、配列を2つに分けたとき、少なくともどちらかは必ずソートされていることです。

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

のように、右の部分配列はソートされておらず、左の部分配列はソートされているように見えます。

もし、midが回転点であれば、左右両方のサブアレイがソートされます。

[6,7,8,9,1,2,3,4,5]
         ^

しかし どのような場合でも、半分（部分配列）はソートされていなければなりません。 .

各半分の開始要素と終了要素を比較すれば、どちらがソートされているかは簡単に分かります。

どの半分がソートされているかがわかれば、その半分にキーが存在するかどうかがわかります。

その半分にキーがある場合、その半分に対して再帰的に関数を呼び出します。
そうでなければ、残りの半分で再帰的に検索を呼び出す。

各呼び出しで配列の半分を破棄しているため、このアルゴリズムでは O(logN) .

擬似的なコードです。

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid])

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

ここで重要なのは、1つの部分配列は常にソートされていることで、これを利用して配列の半分を捨てることができる。