Самый быстрый способ проиндексировать элемент в отсортированном списке в Python? [closed]
В списках Python есть функция list.index (elem) , которая, к насколько мне известно, запустить за O (n) раз. Однако, если я могу гарантировать, что список будет отсортирован, будет ли это лучшим способом получить индекс элемента?
Будет ли бинарный поиск быстрее возвращать индекс? Кроме того, есть ли способ заставить стандартную библиотеку python выполнять двоичный поиск индекса элемента в списке?
0
задан Adi
24 July 2016 в 02:56
поделиться
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
0
ответ дан Olathe
28 September 2019 в 19:14
поделиться