Python の「 bisect 」というライブラリについてご紹介します。

import bisect

bisect ライブラリは名前のとおり bisection search ーーいわゆる「二分探索法」のための機能を提供するライブラリです。すでにソートされたリストに対して二分探索法を行う関数を提供しています。

具体的には、大きく分けて次の 2 種類の関数が用意されています。

• bisect_xx
• insort_xx

順番に順番に見ていきます。

bisect_xx

名前が bisect から始まる関数は、二分探索法により指定した値が入るべき箇所の「探索」を行います。探索のみを行い、実際の挿入処理は行いません。

import bisect

li = [1, 9, 15, 32]
x = 15

print bisect.bisect_left(li, x)
# => 2

print bisect.bisect_right(li, x)
# => 3

bisect_left() と bisect_right() は、いずれも 2 つの引数を受け取ります。第 1 引数はソート済みのリスト、第 2 引数は検索対象の値です。一方の戻り値は、「第 1 引数のリストに第 2 引数の値を挿入するとすれば、そのインデックスは何になるか」を表す整数値です。

bisect_left() は、同じ値がすでに入っていた場合、その左側に新しい値を挿入するルールのもとに、挿入場所のインデックスを返します。

一方の bisect_right() は、同じ値がすでに入っていた場合に右側に挿入するものとして、そのインデックスを返します。

いずれも lo と hi という引数をオプションで受け取ることができます。 lo はリストの挿入すべき位置の下限を、 hi は上限を指定するために使えます。

print bisect.bisect_left(li, x, lo=0, hi=1)
# => 1

left や right が名前についていない bisect() という関数もあり、これは bisect_right() と同じ挙動をします。

insort_xx

insort から始まるメソッドは、二分探索法により指定した値を適切な位置に「挿入」します。 bisect が探索のみを行うのに対し、こちらの insort は実際の挿入を行います。

bisect.insort_left(li, x)
bisect.insort_right(li, x)

print li  # => [1, 9, 15, 15, 15, 32]

insort_left() ```` insort_right() が受け取る引数は bisect と同様です。第 1 引数に直接変更が加えられるため、戻り値はありません（戻り値は None です）。

left ```` right のルールも bisect と同じで、 insort_left() は挿入できる箇所が複数あったときにいちばん左側に、 insort_right() はいちばん右側に挿入します。

left や right のついていない insort() というメソッドもあり、これは insort_right() と同じ挙動をします。

print bisect.insort(li, x)

オプション引数についても bisect と同じで、範囲を制限するための lo ```` hi というオプション引数があります。

以上です。

参考

• bisect — 配列二分法アルゴリズム — Python 2.7ja1 documentation