☰

在 python 中对排序列表中的元素进行索引的最快方法？

tag-icon • tag-icon python search time indexing
在 python 中对排序列表中的元素进行索引的最快方法？

list.index(elem)据我所知，Python 的列表有一个函数，运行时间为 O(n)。但是，如果我可以保证列表已排序，这仍然是获取元素索引的最佳方法吗？

二分搜索会更快地返回索引吗？此外，有没有办法强制 Python 标准库对列表中元素的索引进行二分搜索？

答案1

是的，二分查找通常更快。不，标准库index函数没有这个选项。

另一个答案有二分查找的代码：

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):   # can't use a to specify default for hi
    hi = hi if hi is not None else len(a) # hi defaults to len(a)   
    pos = bisect_left(a,x,lo,hi)          # find insertion position
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end

相关内容