Binary Search
整数のリスト nums が昇順に並べられて与えられます。値の重複はありません。また、整数 target が与えられます。target が nums に含まれている場合は、0から数えたインデックスを返し、含まれていない場合は -1 を返してください。O(log n) 時間を目指してください。つまり、すべての要素を調べる余裕はありません。
関数
- numsinteger-array
- 重複のない整数のソート済みリスト
- targetinteger
- 探す値
- 戻り値integer
- nums 内の target のインデックス。見つからない場合は -1
制約
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsは厳密な昇順に並んでいるため、各値は一度だけ現れます。
例
- 入力
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- 出力
- 4
- 説明
nums[4]は9です。検索では、まずインデックス3（値は4、小さすぎる）を調べ、次にインデックス5（値は15、大きすぎる）を調べ、その後インデックス4を調べて9を見つけます。
- 入力
- nums = [1, 3, 5, 8, 13, 21]target = 10
- 出力
- -1
- 説明
- 10 は 8 と 13 の間に位置し、どちらも 10 ではないため、リストに含まれていません。検索範囲は
loがhiを超えるまで縮小し、関数は-1を返します。
提出時に隠しテスト+15件
発展問題
もしnumsに重複した値が含まれる可能性がある場合でも、O(log n)のままtargetの最初のインデックスを返すにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リストはソートされています。
targetと中央にある要素を比較すると、その片側にあるすべての要素について何がわかりますか？nums[mid] < targetの場合、nums[mid]とその左側にあるすべての要素は小さすぎるため、targetは右側にしかありません。1回の比較で候補の半分を除外できます。targetがまだ含まれている可能性のあるリストの範囲を、loとhiの2つのインデックスで保持します。中央の要素と比較し、loまたはhiをその要素の先へ移動させ、targetが見つかるか、loがhiを超えたら停止します。
解説
要素を1つずつ調べればtargetが見つかりますが、この問題を興味深くしている重要な事実、つまりリストがソートされていることを無視しています。中央の要素と1回比較するだけで、targetがまだ含まれている可能性のある半分がわかるため、各ステップで候補を半分に絞り込めます。その結果、10^4個の要素を含むリストでも、比較回数は最大14回で済み、10000回の比較は不要です。
左から右へスキャンする
考え方
各インデックスを順に調べ、値がtargetと等しい最初のインデックスを返します。一致するものがないままループが終わった場合、targetはリストに含まれていないため、-1を返します。すべての要素を1回ずつ比較するので、リストがソート済みかどうかにかかわらず、どのリストに対しても正しい答えが得られます。
問題は、この汎用性にあります。要素数が10^4のリストでは、最大10000回の比較が必要になり、処理量はnに比例して増加します。この走査ではnumsがソート済みであることを利用しないため、課題が求めるO(log n)の計算量を実現できません。値がtargetを超えた時点で早期に終了することはできますが、最悪の場合はリスト全体を読み取ることになります。
アルゴリズム
iが0からn-1までの各インデックスについて、nums[i]とtargetを比較します。- それらが等しければ、
iを返します。 - ループの後、
-1を返します。
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -12つのインデックスを使った二分探索
考え方
1 つの条件を維持しながら、lo と hi の 2 つのインデックスを使います。target がリスト内にあるなら、そのインデックスは lo から hi までの範囲内（両端を含む）にあります。開始時点では、その範囲はリスト全体、つまり 0 から n-1 です。中央のインデックス mid を調べます。nums[mid] が target と等しければ、そこで完了です。小さければ、リストはソートされているため、mid までのすべての要素も小さいことになります。そこで lo を mid + 1 に移動します。大きければ、hi を mid - 1 に移動します。どちらに移動しても、この条件は保たれます。
最初の例、[-7, -2, 0, 4, 9, 15, 23] と target = 9 をたどってみましょう。範囲 0 から 6 の中央は 3 で、値は 4 です。小さすぎるため、範囲は 4 から 6 になります。その中央の 5 には 15 があり、大きすぎるため、範囲は 4 から 4 になります。インデックス 4 の値は 9 なので、4 を返します。
target が見つからない場合、lo が hi を超えるまで範囲は縮小し続けます。このとき範囲は空になり、条件から target がどこにもないことが分かるので、-1 を返します。各ステップで範囲は半分になるため、ループの実行回数は最大でもおよそ log2(n) + 1 回です。要素数が 10^4 の場合、14 ステップです。追加で必要なメモリは 2 つのインデックスだけです。
アルゴリズム
lo = 0とhi = n-1を設定します。lo ≤ hiの間、mid = lo + (hi - lo) / 2を計算します。nums[mid]がtargetと等しければ、midを返します。nums[mid] < targetの場合は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[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
落とし穴と境界ケース
二分探索は短いアルゴリズムですが、ほとんどのバグは範囲の端における境界のずれです。
hiを最後のインデックスにして、lo < hiでループする。候補が1つ未確認のままループが停止するため、nums = [5]でtarget = 5の場合、-1が返されます。両端を含む範囲では、lo ≤ hiの間ループします。- 両端を含む範囲で、
lo = midまたはhi = midに更新する。loとhiが隣り合っていると、midはloと等しくなり、範囲が縮まりません。つまり、無限ループになります。nums[mid]はすでに確認済みなので、mid + 1またはmid - 1でその先に進みます。 - 固定幅整数で
(lo + hi) / 2を計算する。インデックスが約10^9を超えると、合計がオーバーフローします。ここでの上限はそれよりはるかに小さいですが、lo + (hi - lo) / 2を使うのが安全な習慣です。 targetが見つからないときにloを返す。ループ終了後のloは挿入位置であり、有効なインデックスです。-1ではありません。- LuaとRでのずれを忘れる。これらのリストは1から始まるため、返すインデックスは位置から1を引いた値です。
よくある質問4
二分探索の時間計算量はどれくらいですか？
O(log n)。比較するたびに、ターゲットがまだ含まれている可能性のある範囲が半分になるため、kステップ後に残る候補は最大でもn / 2^k個です。要素数が10^4のリストでは比較は最大14回、要素数が10^9のリストでは最大30回必要です。反復版では追加の領域をO(1)使用します。
二分探索にソート済みの配列が必要なのはなぜですか？
リストの半分を除外する手順は、要素の順序に依存します。nums[mid] < target のとき、ソートされていれば、mid より左のすべての要素も target より小さいことが保証されるため、一致するものはありません。ソートされていないリストでは、この比較から他の要素については何も分からず、すべてを確認する必要があります。
二分探索は反復的に行うべきですか、それとも再帰的に行うべきですか？
どちらも正しく、どちらも O(log n) 時間で実行されます。再帰版は片方の半分に対して自身を呼び出し、スタック領域を O(log n) 使用します。反復版はループ内で lo と hi を動かし、O(1) 使用します。面接官は通常ループを期待し、再帰の上限も回避できます。
中央のインデックスを計算するときに、オーバーフローを避けるにはどうすればよいですか？
(lo + hi) / 2ではなくmid = lo + (hi - lo) / 2と書きます。どちらも同じインデックスになりますが、後者の形式では先に2つのインデックスを加算するため、32ビット整数ではインデックスが約1.07 × 10^9を超えると、その合計がオーバーフローします。PythonとRubyは整数に上限がないため、そちらでは短い形式でも安全です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def search(nums, target):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
期待値
4