在元组列表上使用二等分，但仅使用第一个值进行比较

Question

我阅读了有关如何bisect在元组列表上使用的问题，并使用该信息来回答该问题。它有效，但我想要一个更通用的解决方案。

由于bisect不允许指定key函数，如果我有这个：

import bisect
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)]

我想找到x > 5这些(x,y)元组的第一个项目（根本不考虑y，我目前正在这样做：

bisect.bisect_left(test_array,(5,10000))

我得到了正确的结果，因为我知道noy大于 10000，所以将bisect我指向(7,8). 如果我1000换了，那就错了。

对于整数，我可以做

bisect.bisect_left(test_array,(5+1,))

但在可能有浮点数的一般情况下，如何在不知道第二个元素的最大值的情况下做到这一点？

test_array = [(1,2),(3,4),(5.2,6),(5.2,7000),(5.3,8),(9,10)]

我试过这个：

bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon,))

它没有用，但我试过这个：

bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon*3,))

它奏效了。但这感觉就像一个糟糕的黑客。任何干净的解决方案？

Answer 1

bisect支持任意序列。如果您需要使用bisect密钥，而不是将密钥传递给bisect，您可以将其构建到序列中：

class KeyList(object):
    # bisect doesn't accept a key function, so we build the key into our sequence.
    def __init__(self, l, key):
        self.l = l
        self.key = key
    def __len__(self):
        return len(self.l)
    def __getitem__(self, index):
        return self.key(self.l[index])

然后您可以使用bisectwith a KeyList, 具有 O(log n) 性能，无需复制bisect源代码或编写自己的二进制搜索：

bisect.bisect_right(KeyList(test_array, key=lambda x: x[0]), 5)