Pythonの二分探索
二分探索は比較ごとに探索範囲を半分に減らします。
Pythonの二分探索とは？
二分探索は比較ごとに探索範囲を半分に減らします。
ソート済みリストから値を高速に探します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
Pythonの二分探索のビジュアライザー
O(log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
main.py
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))期待される出力
3仕組み
中央値で左右どちらを残すか決めます。時間O(log n)ですが入力はソート済みである必要があります。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。