python隐式二进制搜索

Question

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

我经常要去看看

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

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

Answer 1

Python喜欢显式的而不是隐式的。如果知道数据已排序，则可以显式使用^{} module，或者使用该模块创建实现__contains__的list子类。你知道吗

例如：

import bisect


class SortedList(list):
    def __contains__(self, elem):
        idx = bisect.bisect_left(self, elem)
        return idx < len(self) and self[idx] == elem

可以用作list的替代，并且in将自动使用__contains__。您可能也希望重写__setitem__、.extend()和.append()以保持列表的排序顺序。你知道吗

Answer 2

我的建议是子类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