Pythonでのupper_boundとlower_boundの理解と活用

Pythonでは、C++のstd::lower_boundやstd::upper_boundに相当する機能がbisectモジュールに存在します。これらの関数は、ソートされたリストに対して二分探索を行い、特定の条件を満たす要素のインデックスを返します。

lower_boundとupper_boundの基本

lower_boundは、指定した値以上の最初の要素のインデックスを返します。一方、upper_boundは、指定した値を超える最初の要素のインデックスを返します。

例えば、以下のようなリストがあるとします。

a = [1, 1, 2, 2, 2, 3, 3]

このリストで、2をキーとした場合、lower_boundとupper_boundは以下のようなインデックスを返します。

• lower_bound(a, 2)は2が始まる位置、つまりインデックス2を返します。
• upper_bound(a, 2)は2が終わる位置の次、つまりインデックス5を返します。

Pythonでの実装

Pythonでは、bisectモジュールのbisect_left関数とbisect_right関数を使用して、lower_boundとupper_boundを実装できます。

import bisect

a = [1, 1, 2, 2, 2, 3, 3]
x = 2

# lower_bound
index = bisect.bisect_left(a, x)
print(index)  # Output: 2

# upper_bound
index = bisect.bisect_right(a, x)
print(index)  # Output: 5

このように、Pythonのbisectモジュールを使用することで、効率的にlower_boundとupper_boundを計算することができます。これらの関数は、データ構造やアルゴリズムを扱う際に非常に便利です。