C++のstd::lower_bound()とPythonでの話。

けんちょん本を読むと・・・

けんちょん本ってAmazonで検索すると出るんですね。知らなかった。

本題に戻りますが、この本には二分探索法の章があります。

C++の話

その中でC++のライブラリであるstd::lower_bound()を使う際に得られる情報について記述があります。

std::lower_bound()の使用自体はソート済みの配列aとkeyが存在するかという内容のライブラリです。
もう少し具体的に記述すると、a[i] >= keyという条件を満たす最小の添字iを返す(この時の計算量は配列Nに対してO(logN))、というものなのですが、これは単に配列の中に存在するか否か、だけのライブラリではないという事みたいです。

例えば、

• 配列のなかにkeyが存在しない場合、与えたkey以上の値の範囲での最小値を取得

• 配列のなかに値keyが複数あった時、その内の最小の添字を取得

といったような使い方があるようで、これについて学んだ時、Pythonで似たようなライブラリは無いのかパッと思い浮かばなかったので、調べてみました。

Pythonの話

Pythonではbisectが該当するようで、何度か使ったことはあったが詳しい仕様を思い出せなかったので、実際にドキュメントを読みながら使い方を見てみました。

import bisect

a = [3,8,11,18,27,31]

bisect.bisect_right(a,20) # 4

print(bisect.bisect_right(a,11)) # 3

print(bisect.bisect_left(a,11)) # 2

この配列に18を足してみましょう。するとbisectは以下のような振る舞いをします。

import bisect

a = [3,8,11,18,18,27,31]

bisect.bisect_right(a,18) # 5

bisect.bisect_left(a,18) # 3

lower_boundはbisect_leftに、upper_boundはbisect_rightと同様の振る舞いをするようです。

様々な使い方ができそうです。気になる方はぜひけんちょん本を買いましょう。損はありません。むしろ得します。