Python でバイセクションサーチ（二分探索法）を行う方法をご紹介します。

Python にはそのままずばり「 bisect 」――バイセクションサーチを行うためのライブラリが用意されています。

実際の使い方を見てみましょう。

from bisect import bisect_left, bisect_right

li = [1, 3, 5, 6, 10, 14, 17, 22, 30, 35]

index_left = bisect_left(li, 6)  # => 3
index_right = bisect_right(li, 6)  # => 4

bisect_left bisect_right はソート済みのリストに新たな値を入れようとしたときに、入れるべき場所を返してくれる関数です。新たな値がすでにリストに存在する場合には、 bisect_left はなるべく左側に、 bisect_right はなるべく右側に入れようとします。

上記の例では 6 を追加するなら、入れるべき場所は次のふたつのうちのどちらかです。

[1, 3, 5, __here__, 6, 10]
[1, 3, 5, 6, __here__, 10]

上の場合のインデックスは 3 、下の場合のインデックスは 4 で、それぞれ bisect_left 、 bisect_right の戻り値が示すものと一致します。

さらに bisect_left bisect_right には範囲を制限するための引数を渡すこともできます。こんな感じ。

bisect_left(対象リスト, 探したい値, lo=左側のインデックス, hi=右側のインデックス)

実際に二分探索の結果、値を挿入したい場合には insort_left insort_right を使います。

from bisect import insort_left

bisect.insort_left(li, new_element)

insort_left insoft_right はいずれも引数に与えたリストを変更する（破壊的な）メソッドです。

参考

• bisect — Array bisection algorithm - Python 公式ドキュメント