バグのない基本的な二分探索
low、high、mid のループを確実に実装します
「バグのない基本的な二分探索」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
探索範囲を半分にする
二分探索は、ソート済みのリストで各ステップの範囲を半分にして値を見つけます。これにより、遅い O(n) の走査が高速な O(log n) の探索になります。
a = [1, 3, 5, 7, 9] # must be sortedソート済みであることが必須
二分探索はソート済みのデータでしか機能しません。リストが順不同なら、まずソートしてください。そうしなければ結果は意味を持たず、誤ったものになります。
a.sort() # ascending order required二つの境界
二つのポインタから始めます。low はインデックス 0 に、high は最後のインデックスに置きます。対象の値が存在するなら、必ずこの範囲内にあります。
low, high = 0, len(a) - 1中央を安全に求める
mid は low + (high - low) // 2 として計算します。Python ではオーバーフローは問題になりませんが、この形をどこでも使える安全な習慣として身につけてください。
mid = low + (high - low) // 2三つの結果
a[mid] と target を比較します。見つかった、小さすぎる、大きすぎるのいずれかです。それぞれの場合で範囲の狭め方が異なります。
if a[mid] == target:
return mid小さすぎるなら右へ
a[mid] が target より小さい場合、答えは必ず右側にあります。low を mid + 1 に移し、左半分を捨ててください。
elif a[mid] < target:
low = mid + 1大きすぎるなら左へ
a[mid] が target より大きい場合は、左半分を探索します。high を mid - 1 に移せば、mid をもう一度調べずに済みます。
else:
high = mid - 1ループ条件
low が high 以下である間、処理を続けます。二つが交差したら範囲は空であり、target は存在しません。
while low <= high:
mid = low + (high - low) // 2見つからない場合を示す
一致するものがないままループが終了した場合、その値は存在しません。呼び出し側が成功と失敗を区別できるよう、慣例として -1 を返します。
return -1 # target not in listオフバイワンの罠
典型的なバグは、ポインタを動かすときに+1 または -1を付け忘れることです。忘れると mid が永遠に再検査され、無限ループになります。
low = mid + 1 # not low = mid使えるならライブラリを使う
単純なメンバーシップテストなら、Python の bisect モジュールにバグのない探索機能が用意されています。独自の処理が必要な場合だけ、ループを自分で書いてください。
import bisect
i = bisect.bisect_left(a, target)確認
ループを正しく進め続けるものは何か考えてみてください。
まとめ：バグのない探索
これで low と high を設定し、mid を安全に計算し、適切な側を狭め、オフバイワンの罠を避けられるようになりました。対数時間の探索を使いこなせます。🎯
よくある質問
「バグのない基本的な二分探索」レッスンは無料ですか？
はい。「バグのない基本的な二分探索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「バグのない基本的な二分探索」で何を学びますか？
low、high、mid のループを確実に実装します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「バグのない基本的な二分探索」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。