python - 如果我需要查找一个值或下一个最高值，我应该使用什么搜索算法？

Question

我将有一个交易 ID 的有序列表，如下所示:

41025745
41025741
41025740
41025739
41025738
41025735
41025721
41025719
41025718
41025717
41025699
41025683
41025682
41025681

从 10 到 1000 之间的任何值，具体取决于我根据 API 调用计算出我想要一次获取的数量。

假设我想查找事务 ID 41025735(在列表中)，我可以使用二分搜索来查找它，但如果我想查找 41025736(不在列表中)，我将返回 41025738，即下一个最高值。我应该用什么？修改后的二分查找？

Answer 1

bisect module直接支持，但要求输入按升序排列:

>>> from bisect import bisect_left

>>> data = '''\
41025745 41025741 41025740
41025739 41025738 41025735 41025721
41025719 41025718 41025717 41025699
41025683 41025682 41025681'''

>>> trans_ids = sorted(s.split())
>>> def find_ge(a, x):
        'Find leftmost item greater than or equal to x'
        i = bisect_left(a, x)
        if i != len(a):
            return a[i]
        raise ValueError

>>> find_ge(trans_ids, '41025736')
'41025738'