このブログでは、Pythonの二分探索をわかりやすく解説！
学校の授業で学んだ内容を復習できるだけでなく、授業を休んだ人も自学が可能です。
アルゴリズムの基本から、コードの解説、間違いやすいポイントまでカバー。
理解を深め、効率的な検索方法をマスターしよう！
プログラミング初心者でも安心の丁寧な説明付き。
高校生向けの試験対策にも最適な内容です。
二分探索って何？
二分探索（Binary Search）は、ソート済みのリスト から素早く値を探すアルゴリズムです。
例えば、辞書で単語を探すとき、最初のページから順に探すのではなく、真ん中のページを開いて探す単語が前後どちらにあるかを判断して範囲を絞る方法と同じです。
二分探索のポイント：
- リストがソートされていることが前提
- 探索範囲を毎回 半分 に減らすので、効率が良い
- 大きなデータでも高速に検索可能
二分探索の手順
- リストの中央の値 を調べる
- 探したい値が中央の値と同じなら「見つかった！」
- 小さい場合は「左側」を探索、大きい場合は「右側」を探索
- これを繰り返して、見つける or 探索範囲がなくなったら終了
Pythonで二分探索を実装してみよう！
# ループを使った二分探索
def binary_search(arr, target):
left = 0 # 探索範囲の左端
right = len(arr) - 1 # 探索範囲の右端
while left <= right: # 探索範囲が有効な間、繰り返す
mid = (left + right) // 2 # 中央のインデックスを求める
if arr[mid] == target: # 中央の値が探している値なら
return mid # インデックスを返す
elif arr[mid] < target: # 中央の値が小さいなら
left = mid + 1 # 右側の範囲を探索
else: # 中央の値が大きいなら
right = mid - 1 # 左側の範囲を探索
return -1 # 見つからなかった場合
# 動作確認
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(numbers, target)
if result != -1:
print(f"{target}はインデックス{result}にあります。")
else:
print(f"{target}はリスト内にありません。")解説：
left = 0とright = len(arr) - 1で探索範囲の初期値を設定。while left <= right:で探索範囲がなくなるまで繰り返す。mid = (left + right) // 2で中央のインデックスを求める。if arr[mid] == target:で中央の値がターゲットならインデックスを返す。elif arr[mid] < target:なら、右側 (left = mid + 1) を探索。else:なら、左側 (right = mid - 1) を探索。- ループが終わっても見つからなければ
return -1で「見つからなかった」とする。
エラーが出たら…：
mid = (left + right) // 2 と、if arr[mid] == targetの間に、print(f”探索範囲: left={left}, right={right}, mid={mid}, 値={arr[mid]}”) を入れてみましょう。
探索範囲の変化を見ることができるようになります！
間違いやすいポイント
- リストが順番通りに並び替えがされていないと正しく動作しない！
numbers = [10, 2, 8, 6, 4, 12, 14, 16]のような順番通りになっていないリストでは、正しく検索できません。- 必ず順番通りに並び替え済みのリストを用意しましょう。
- 探索範囲の更新を間違えやすい！
left = mid + 1とright = mid - 1の更新を間違えると、無限ループになる可能性があります。- 「小さい場合は左を狭める、大きい場合は右を狭める」を意識しましょう。
- 整数除算
//を使う！mid = (left + right) / 2ではなく、mid = (left + right) // 2を使いましょう。//は整数除算で、リストのインデックスに適した値を取得できます。
- 対象が見つからなかった場合の戻り値を確認！
return -1にしておかないと、見つからなかったときにエラーになる可能性があります。- 例えば、
if result != -1:のように-1を考慮してコードを書きましょう。
実践問題
問題1
次のリストで 10 のインデックスを求めるプログラムを書いてみよう！
numbers = [2, 4, 6, 8, 10, 12, 14, 16]
問題2
二分探索は 「ソートされたリスト」 でないと正しく動作しません。
試しに、ソートされていないリスト numbers = [10, 2, 8, 6, 4, 12, 14, 16] で試すとどうなるでしょうか？
まとめ
- 二分探索は、ソート済みリストで使える高速な探索アルゴリズム
- 実際にコードを書いて試してみよう！
質問があれば、コメントで質問してください！
コメント