ライブラリbisectによる二分探索【Python】

AtCoderなどの競技プログラミングを行っていると二分探索を使う場面があります。

線形探索と比較して大きなデータに対しても短い時間で処理できることが利点です。

この二分探索を行うライブラリがbisectで、使い方を記事にしたいと思います。

ソート

import bisect

A = [0, 1, 10]
B = [0, 10, 1]

num_A = bisect.bisect(A,5)
num_B = bisect.bisect(B,5)

print(num_A) # -> 2
print(num_B) # -> 1

二分探索を行う対象のリストはソート済みであることが必要です。

誤って未ソートのリストに対して使用した場合は間違った答えを返すので注意してください。

上のコードのようにソート済みのAと未ソートのBではbisectの値が異なり、ソートされていない方の答えnum_Bは間違いです。

ライブラリのimport

import bisect

bisectを使用するときはライブラリをインポートする必要がありますので、インポートを忘れずに行います。

bisectとbisect_right

import bisect

A = [0, 1, 10, 100, 1000, 10000]

num = bisect.bisect(A,5)

print(num) # -> 2

上のコードのようにソート済みのリストに対してbisectを使うと、リストに挿入できるインデックスを返します。
5はA[1] = 1 とA[2] = 10の間に挿入することが正しいので返す値は2です。

import bisect

A = [0, 1, 1, 2, 2, 3, 3]

num = bisect.bisect(A,2)
num_right = bisect.bisect_right(A,2)

print(num) # -> 5
print(num_right) # -> 5

すでにリストに含まれている値を探索するとき、bisectとbisect_rightは探索する値の後ろを挿入点として返します。

上のコードではリストの2と、次の値の3の間を挿入点とするので返す値は5です。

bisect_left

import bisect

A = [0, 1, 1, 2, 2, 3, 3]

num = bisect.bisect(A,2)
num_left = bisect.bisect_left(A,2)

print(num) # -> 5
print(num_left) # -> 3

bisect_rightは探索する値の後ろを挿入点として返しましたが、bisect_leftを使えば値の前のインデックスを返します。

この例ではbisect_leftを使用すると、探索する値の2と その前の値1の間を挿入点とするので返す値は3になります。

このようにbisectライブラリを使用することで簡単に二分探索を行うことができます。

競技プログラミングでもいい成績を残せるよう活用していきたいですね！