python隐式二进制搜索

Question

我有一张已经整理好的单子。你知道吗

我经常要去看看

if foo in sortedlist:
    pass  # not really.  but not the point.

有没有办法教“in”排序列表是排序的，它应该二进制搜索列表？你知道吗

Answer 1

我的建议是子类list来使用排序list：

from bisect import bisect_left
class SortedList(list):
    def __init__(self, l):
        list.__init__(self, sorted(l))
    def __contains__(self, obj):
        pos = bisect_left(self, obj, 0, len(self))
        return (pos != len(self) and self[pos] == obj)

然后：

>>> l = SortedList([4,3,5435,123,54,2,343,23])
>>> l
[2, 3, 4, 23, 54, 123, 343, 5435]
>>> 23 in l
True
>>> 25 in l
False
>>> 123122 in l
False
>>> -1 in l
False