Search in Rotated Sorted Array
相異なる整数のリストが昇順に並べられた後、回転されています。つまり、先頭から0個以上の要素を取り出し、同じ順序のまま末尾に移動しています。たとえば、[2, 5, 8, 11, 15, 19, 23]を4つ分回転すると、[15, 19, 23, 2, 5, 8, 11]になります。回転したリストnumsと整数targetが与えられます。targetがnums内にある場合は0から数えたインデックスを、ない場合は-1を、O(log n)時間で返してください。
関数
- numsinteger-array
- 回転された、重複のない整数のリスト
- targetinteger
- 探す値
- 戻り値integer
- nums 内の target のインデックス。見つからない場合は -1
制約
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- すべての
numsの値は互いに異なります。 numsは、あるkだけ回転させた昇順リストです。ただし、0 ≤ k < nums.lengthであり、k = 0の場合は回転していません。
例
- 入力
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- 出力
- 4
- 説明
- 最初の中央の要素であるインデックス3には2があり、右半分の
[2, 5, 8, 11]はソート済みで、5を含んでいます。次の中央の要素であるインデックス5には8があり、ソート済みの左側部分[5, 8]には5が含まれているため、インデックス4に進みます。
- 入力
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- 出力
- -1
- 説明
- 65 は 60 と 70 の間に位置し、それを保持する要素はありません。最初の中央の値である 70 によって、65 はソート済みの左側の部分
[40, 50, 60, 70]に入るため、範囲はそこで空になるまで縮小します。
- 入力
- nums = [8, 13, 21, 1, 3, 5]target = 13
- 出力
- 1
- 説明
- 最初の中間位置であるインデックス 2 には 21 があります。左側の部分
[8, 13, 21]はソート済みで、13 は 8 と 21 の間にあるため、右側の部分を除外します。その後、検索によってインデックス 1 にある 13 が見つかります。
発展問題
numsに重複が含まれる可能性がある場合、どのアルゴリズムもO(log n)を保証できません。単一の0を隠す、1だけからなる回転リストを使って証明できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
任意の中央のインデックスを選び、その両側にある2つの半分を見てみましょう。回転によって、値が最大から最小へと下がる箇所が1つできています。その下がる箇所が両方の半分に含まれることはありますか？
少なくとも片方の半分は常にソートされており、
nums[lo]とnums[mid]を比較すれば、どちらかがわかります。ソートされている半分については、targetがその最初の値と最後の値の間にあるかどうかを1ステップで確認できます。targetをまだ含む可能性のある範囲を、loとhiで保ちます。各ステップで、ソート済みの半分の値の範囲にtargetが含まれている場合はその半分を保ち、そうでなければもう一方を保ちます。targetを見つけるか、範囲が空になるまで続けます。
解説
回転されたソート済みリストは、2つのソート済み区間から成ります。[15, 19, 23]、続いて[2, 5, 8, 11]です。targetと中央の値を比較しても、どちら側にあるかはもう分かりません。しかし、リストをどこで分割しても、少なくとも一方の半分はソート済みであり、比較を1回すればtargetがその半分にある可能性があるかどうか分かります。
すべての要素をスキャンする
考え方
すべてのインデックスを確認し、値がtargetと等しい最初のインデックスを返します。ループの後には-1を返します。すべての要素を読み取るため、どのようなリストに対しても正しく動作します。2つのソート済みの区間を活用していません。5000個の要素では最大5000回の比較が必要ですが、二分探索なら13回で済みます。
アルゴリズム
- 0 から
n-1までの各インデックスiについて、nums[i]とtargetを比較します。 - それらが等しければ、
iを返します。 - ループの後で、
-1を返します。
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1回転点を見つけてから、二分探索する
考え方
2つ目のランは最小値から始まります。そのインデックスをkとします。nums[k..n-1]とnums[0..k-1]はどちらもソートされており、1つ目のランのすべての値は2つ目のランのすべての値より大きくなっています。kがわかれば、targetとnums[k]、nums[n-1]を比較して対象のランを選び、通常の二分探索で見つけられます。
kを見つけるには、中央の値とnums[hi]を比較します。nums[mid] > nums[hi]の場合、値はmidより後のどこかで下がるため、最小値はその右側にあります。そうでない場合、nums[mid..hi]は途中で下がることなく増加しているため、最小値はmidまたはその前にあります。最初の例では、中央の値は2、19、23となるので、k = 3です。また、5はnums[3] = 2とnums[6] = 11の間にあります。二分探索を2回行うと、ステップ数は約2 log2 nです。
アルゴリズム
lo = 0とhi = n-1を設定します。lo < hiの間、midを計算します。nums[mid] > nums[hi]の場合はlo = mid + 1を設定し、そうでない場合はhi = midを設定します。- 最終的なインデックス
kが最小値を保持します。 nums[k] ≤ target ≤ nums[n-1]の場合は、インデックスkからn-1までを二分探索します。そうでない場合は、0 からk-1までを探索します。- 見つかったインデックスを返します。範囲が空になった場合は
-1を返します。
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1ソート済みの半分に対して二分探索を1回行う
考え方
二分探索の約束を守りましょう。targetがリストにあるなら、そのインデックスはloとhiの間にあります。リスト全体で値が下がるのは1回だけなので、midを境にした2つの半分のうち、値の下がる箇所を含むのは多くても一方だけで、もう一方はソート済みです。nums[lo] ≤ nums[mid]なら左半分がソート済みで、そうでなければ右半分がソート済みです。
ソート済みの半分では、両端の値を使った範囲判定によって、targetがその中にあるかどうかを判断できます。たとえば左半分ならnums[lo] ≤ target < nums[mid]です。中にある可能性があればそこを探索し、なければtargetはもう一方の半分にしかありません。各ステップで範囲は半分になります。要素数が5000なら、最大13ステップです。
アルゴリズム
lo = 0とhi = n-1を設定します。lo ≤ hiの間、midを計算し、nums[mid]がtargetと等しければそれを返します。nums[lo] ≤ nums[mid]の場合、左半分はソート済みです。nums[lo] ≤ target < nums[mid]のときはhi = mid - 1を設定し、それ以外の場合はlo = mid + 1を設定します。- それ以外の場合、右半分はソート済みです。
nums[mid] < target ≤ nums[hi]のときはlo = mid + 1を設定し、それ以外の場合はhi = mid - 1を設定します。 - ループが終了したら、
-1を返します。
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
落とし穴と境界ケース
nums[lo] < nums[mid]と書き、≤を使わない。要素が2つ残っている場合、midはloと等しくなり、この厳密な判定では[9, 4]をソート済みの右半分とみなしてしまうため、target = 4で-1が返される。- 最初に
targetとnums[mid]を比較する。最初の例でtarget = 19の場合、中央の値2はそれより小さいため、探索は右に進み、インデックス1を見落とす。 - ソート済みの半分の片端だけを調べる。
[40, 50, 60, 70, 80, 10, 20]でtarget = 80の場合、target ≥ nums[lo]だけで判定すると、探索は[40, 50, 60, 70]に進んでしまう。 - Rustでは、
usizeに対するk - 1は、回転していないリストでk = 0のときにアンダーフローする。半開区間を使う。 - LuaとRでは、1始まりの位置を返してしまう。1を引く。
よくある質問3
回転したソート済み配列を検索する場合の時間計算量はどのくらいですか？
O(log n)時間、追加の領域はO(1)です。各ステップで範囲の半分を残すため、5000個の要素でも最大13ステップで済みます。最初に回転点を見つける方法もO(log n)で、ステップ数は約2倍になります。
配列に重複する値が含まれている場合でも、このアルゴリズムは動作しますか？
記述どおりではありません。nums[lo]、nums[mid]、nums[hi]が等しい場合、どちらの半分がソート済みであるかも証明できません。一般的な対処法では、その場合にloを1つ進めます。これにより答えの正しさは保たれますが、最悪の場合の計算量はO(n)になります。
まず回転点を見つけるべきですか、それとも1回の走査で探すべきですか？
どちらも O(log n) で実行されます。最初に最小値を見つける方法では、問題を2つの通常の二分探索に分けます。1回のパスで探索する方法は、1つのループでより少ない手順で処理でき、多くの面接官が期待する方法です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def search(nums, target):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
期待される出力
4