Pythonのbisectの返す結果に戸惑った、 と同僚に話したところ、「いや他の言語のライブラリも大体同じですよ」 と言われたわけです。

戸惑った部分ですが、新人プログラマー野田さんの課題を 解いている過程で、「指定した金額以下で一番大きい金額のインデックス」が欲しい、と思ったのですよね。 結局それはbisect.bisect_leftを使って解決したんだけど、 bisect_leftの場合「返り値のインデックスの更に1コ前」が欲しい値だったわけです。

改めて二分探索の挙動について調べたところ、少なくともPython, Java共に、 あるデータが「挿入されてもソート状態が保たれる箇所」を探索してくれるものらしい。

例えば以下はPythonの例。

1
2
3
4
5
6
7
8

import bisect

a = [1, 2, 4, 8, 11]
data = 6
i = bisect.bisect(a, data)
# i の値は 3
a.insert(i, data)
# a の値は [1, 2, 4, 6, 8, 11]

なるほど。納得。

とは言え、カスタムの条件で二分探索したいケースもあると思うんですよね。例えば接尾辞配列のように。

超簡単な例だと、こういうイメージ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

txt = 'banana'
suf = [i for i in range(len(txt))]
# suf の値は [0, 1, 2, 3, 4, 5]

suf.sort(key=lambda i: txt[i:])
# suf の値は [5, 3, 1, 0, 4, 2]

print([txt[i:] for i in suf])
# ['a', 'ana', 'anana', 'banana', 'na', 'nana'] が出力される。
# この結果は、全部分文字列がソートされた状態
## a
## ana
## anana
## banana
## na
## nana
# sufにはソートされた状態の各部分文字列へのインデックスが格納されている。
# この中から、例えば'an'が含まれる全ての箇所を探す、というのはbisectでは探索できない…

こういう用途用の二分探索は、接尾辞配列ライブラリに含まれてると思うんですけどね。

少なくともPythonで言うと、リストの外の情報を使ってソートすることはできるけれど、 それに対する二分探索による探索がないのはちょっと不便な気がしたのです。 それを可能とするライブラリがあるのであれば、それを使うにして、 なければそれを実現するライブラリを作ろうかしら。

「それ～～でできるよ」情報があったらお教え下さいませ。