Search in Rotated Sorted Array

各インデックスを順番に調べ、値が target と等しい最初のインデックスを返します。一致するものがないままループが終了した場合は、-1 を返します。値は重複しないため、最初の一致が唯一の一致であり、リストが回転しているかどうかにかかわらず、この走査は正しく動作します。

この方法は、問題文で説明されていることをすべて無視しています。リストはソート済みの2つの区間から成っていますが、この走査では最大5000個すべての要素を調べます。一方、二分探索なら比較は約13回で済みます。入力サイズが大きくなるほど差は広がり、要素が100万個なら比較回数は100万回ですが、二分探索なら約20回です。問題が求めているのは O(log n) なので、これは答えではなく、改善の基準となる方法です。

回転されたリストは、ソート済みの2つの区間からなり、2つ目の区間は最小値から始まります。そのインデックスをkとします。kがわかれば、あとは通常の二分探索に置き換えられます。nums[k..n-1]はソート済みで、nums[k]からnums[n-1]までの値を含み、nums[0..k-1]もソート済みで、それより大きい値をすべて含みます。targetとnums[k]およびnums[n-1]を1回比較すれば、どちらの区間を探索するかを選べます。

kを見つけるには、値が下がる位置を二分探索します。中央の値と、範囲の最後の値であるnums[hi]を比較します。nums[mid] > nums[hi]なら、midより後のどこかで値が下がっているため、最小値は右側にあります。そこでlo = mid + 1とします。そうでなければ、nums[mid..hi]は下がることなく増加しているため、最小値はmidかその前にあります。midを範囲内に残すため、hi = midとします。loとhiが一致したとき、そのインデックスがkです。

最初の例、[15, 19, 23, 2, 5, 8, 11]でtarget = 5の場合を追ってみましょう。中央の2は11より大きくないので、hiは3になります。次に、19は2より大きいので、loは2になります。続いて、23は2より大きいので、loは3となり、k = 3です。5はnums[3] = 2とnums[6] = 11の間にあるため、インデックス3から6を探索し、二分探索でインデックス4にある5が見つかります。二分探索を2回行うと、計算量は約2 log2 nステップです。

回転点がどこにあるかを知る必要はありません。二分探索の基本を守りましょう。targetがリスト内にあるなら、そのインデックスはloとhiの間にあります。中央のインデックスmidを見ます。リスト全体で値が下がるのは一度だけなので、その下がり目はmidを境にした2つの半分のうち、多くても片方にあり、もう一方はソートされています。

比較を1回行って、ソートされている半分を見つけます。nums[lo] ≤ nums[mid]なら、左半分のnums[lo..mid]には下がり目がなく、ソートされています。nums[mid]がtargetではないとすでに分かっているので、targetがその半分にあるのはnums[lo] ≤ target < nums[mid]の場合だけです。そうならhi = mid - 1に設定します。そうでなければ、targetはもう一方の半分にしかないので、lo = mid + 1に設定します。nums[lo] > nums[mid]の場合、下がり目は左側にあり、右半分のnums[mid..hi]はソートされています。対称的な条件nums[mid] < target ≤ nums[hi]で判定できます。ソートされていない半分について直接考えることはありません。ソートされた半分にtargetがない場合に限り、もう一方にあると判断できます。

最初の例、[15, 19, 23, 2, 5, 8, 11]でtarget = 5の場合をたどってみましょう。範囲0から6の中央は3で、値は2です。15は2より大きいため、右半分の[2, 5, 8, 11]はソートされており、5はその中にあるので、loを4にします。範囲4から6の中央は5で、値は8です。ここでnums[4] = 5 ≤ 8なので、左半分の[5, 8]はソートされており、5を含んでいます。そこでhiを4にします。インデックス4の値は5です。4を返します。

通常の二分探索と同様に、各ステップで範囲が半分になるため、ループの実行回数は最大でもおよそlog2(n) + 1回です。要素数が5000個なら13ステップで、追加のメモリはインデックス2つ分です。