二分探索を行う

二分探索は整列済み配列を半分ずつ絞り込み、O(log n)時間で探索します。入力が同じ順序で整列されていることが前提です。

二分探索は整列済み配列を半分ずつ絞り込み、O(log n)時間で探索します。入力が同じ順序で整列されていることが前提です。仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。

基本の考え方

二分探索は整列済み配列を半分ずつ絞り込み、O(log n)時間で探索します。入力が同じ順序で整列されていることが前提です。

計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。

手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。

from bisect import bisect_left

values = [2, 5, 8, 12, 20]
index = bisect_left(values, 8)
print(index, index < len(values) and values[index] == 8)

重複値の最初の位置、空配列、未発見値で二分探索の結果を確認してください。