python隐式二进制搜索

Question

我有一个已经排序的列表。

我经常需要检查看看

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

有没有一种方法可以教“in”排序列表已排序并且应该对列表进行二进制搜索？

Answer 1

Python 更喜欢显式而不是隐式。您的选择是显式使用 bisect module如果您知道数据已排序，或者创建 list 的子类，使用该模块实现 __contains__。

例如:

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() 以按排序顺序维护列表。