　ソート済みリストの中から指定した値の位置を探す。高速に。

情報源

コード

　挿入位置を取得する。

import bisect
l = ['A', 'B', 'C', 'D', 'E'] # 予めソートしておくこと
bisect.bisect_left(l, 'D');

>>> import bisect
>>> l = ['A', 'B', 'C', 'D', 'E'] # 予めソートしておくこと
>>> bisect.bisect_left(l, 'D');
3

　存在しない値は末尾を指す。

import bisect
l = ['A', 'B', 'C', 'D', 'E'] # 予めソートしておくこと
bisect.bisect_left(l, 'Z');

>>> import bisect
>>> l = ['A', 'B', 'C', 'D', 'E'] # 予めソートしておくこと
>>> bisect.bisect_left(l, 'Z');
5

　中間にある値より小さいか大きいかを繰り返すことで、高速に検索できる。

　こんな感じで検索するはず。

　探索値Dは中間値Eより小さい。よって、先頭A〜中間-1Dの範囲を対象に、これをくりかえす。

　偶数のため中間はない。そこで中間-1を中間とする。

　検索対象Dは中間値Bより大きい。よって、中間+1C〜末尾の範囲を対象に、これをくりかえす。

位置	リスト	検索位置
2	C	←
3	D

　偶数のため中間はない。そこで中間-1を中間とする。

　検索対象Dは中間値Cより大きい。よって、中間+1D〜末尾の範囲を対象に、これをくりかえす。

位置	リスト	検索位置
3	D	←

　1件しかないため中間値はない。検索対象に一致するならインデックスを返す。さもなくばNoneなり-1なり例外なり、無効を意味する値を返す。

　検索対象Dに一致。これのインデックス3を返す。

　今回の場合、4回目でヒット。これは先頭から順にやったのと同じ回数。ぜんぜん高速じゃない。が、件数が増えるほど、二分探索のほうが少なくて済むはず。

　複数のキーを対象に位置検索したい。

　できないことはないのかもしれない。でもよくわからない。コードもわけわからんくなる。Pythonあるある。

　どうしよう……。

　以下のように公開日時とURLの2キーで一意確認したいのだが、できない。これだとO(N)操作となり高速でなくなるようだ……。

ins_idx = bisect.bisect_left(news_ids, (db_latest_published, db_latest_url))

　それならlist.index(探索値)でいいわ。

　二分探索は複数キーで使えない。

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1218 SMP Tue May 14 00:48:17 BST 2019 armv7l GNU/Linux