Pythonで二分探索: bisectの使い方メモ

bisect は python で二分探索を実行できるライブラリです。

主に bisect_left, bisect_right の2つの関数が重要です。これらの関数は、ある値がリストの何番目に挿入されるかを計算してくれます。

利用の際の注意

二分探索を実行するため、探索するリストの数値はソートされている必要があります。

#以下のように小さい順にソートされている必要がある
List = [10, 20, 30, 30, 40, 60]

使い方は簡単で、第一引数にリスト型(ソート済み)、第二引数は探索する値です。

#使い方
bisect.bisect_left(List, value)
bisect.bisect_right(List, value)

この関数は、$\mathrm{List[i-1]} < \mathrm{value} \leqq \mathrm{List[i]}$ となるインデックス $i$ を返します。

実行例

List = [10, 20, 30, 30, 40, 60]
#例1
bisect.bisect_left(List, 50) #5
#例2
bisect.bisect_left(List, 30) #2

例1を見ると、$\mathrm{List[4]} = 40 < 50 \leqq \mathrm{List[5]}=60$ が成り立つため、5が返されます。

例２のように同じ数値が List の中にある場合、左側 (すなわち、最小のインデックス) が選ばれます。この場合、30という数値が$\mathrm{List}$ のインデックスが 2,3 に存在しているので、最も小さい 2 が選択されます。

この関数の場合は、$\mathrm{List[i-1]} \leqq \mathrm{value} < \mathrm{List[i]}$ となるインデックス $i$ を返します。

実行例

List = [10, 20, 30, 30, 40, 60]
#例1
bisect.bisect_right(List, 15) #1
#例2
bisect.bisect_left(List, 30) #4

例1では、$\mathrm{List[0]} = 10 \leqq 15 < \mathrm{List[1]}=20$ が成立するため、1 が返されます。

例２のように同じ数値が List の中にある場合、右側 (すなわち、最大のインデックスの後ろ) が選ばれます。この場合、30という数値が $\mathrm{List}$ のインデックスが 2,3 に存在しているので、最も大きい 3 の後ろの 4 が選択されます。

インデックス 3 ではなく 4が選択されることに注意が必要です。

これらは、それぞれ bisect_left, bisect_right で探索したインデックスに値を挿入する関数です。

List = [10, 20, 30, 30, 40, 60]
#例1
print(bisect.insort_left(List, 50)) # [10, 20, 30, 30, 40, 50, 60]

bisect_right でも同様の結果となります。

ちなみに、insort_left と insort_right の場合、リスト型でなく np.ndarray 型は使用できません。

pythonの二分探索ライブラリである bisectについてまとめました。

bisect_left では、$\mathrm{List[i-1]} < \mathrm{value} \leqq \mathrm{List[i]}$ となるインデックス $i$ を返します。

bisecct_rightでは、$\mathrm{List[i-1]} \leqq \mathrm{value} < \mathrm{List[i]}$ となるインデックス $i$ を返します。

両方とも式が似ているので注意が必要です。

以下のリンクは公式ドキュメントです。