[解決済み] Pythonによる二項探索（バイセクショ ン）機能

質問

リスト/タプルに対してバイナリサーチを行い、見つかった場合はその項目の位置を、見つからなかった場合は「False」（-1、Noneなど）を返すライブラリ関数はないでしょうか？

の中にbisect_left/rightという関数がありました。 bisectモジュール しかし、それらは項目がリストにない場合でも位置を返します。しかし、私はアイテムがリストにあるかどうかを知りたいだけです（何も挿入したくないのです）。

を使うことを考えました。 bisect_left しかし、それは面倒なようです（さらに、その数字がリストの中で最大の数字より大きくなりうるかどうか境界チェックを行う必要があります）。もっといい方法があれば教えて欲しいです。

編集 何のためにこれが必要なのかを明確にするために。辞書が非常に適していることは承知していますが、メモリ消費量をできるだけ抑えたいのです。私の意図する使い方は、双方向ルックアップテーブルのようなものです。テーブルには値のリストがあり、そのインデックスに基づいて値にアクセスできる必要があります。また、特定の値のインデックスを見つけるか、その値がリストにない場合は None にしたいのです。

このために辞書を使用するのが最も速い方法ですが、必要なメモリが（およそ）2倍になってしまいます。

Pythonのライブラリに何か見落としがあるのではないかと思い、質問させていただきました。Moeが提案したように、自分でコードを書くしかないようです。

どのように解決するのですか？

bisect_left 最初の位置を見つける p は、ソートされた順序を維持したまま、与えられたソート範囲に要素を挿入することができます。 の位置となります。 x もし x が範囲内に存在する。もし p は過去の終了位置です。 x は見つかりませんでした。 そうでなければ x があるかどうかを確認するために x が見つかりました。

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end