Самый быстрый способ индексировать элемент в отсортированном списке в Python?

Question

Самый быстрый способ индексировать элемент в отсортированном списке в Python?

Списки Python имеют функцию list.index(elem) который, насколько мне известно, работает в O(N) времени. Однако, если я могу гарантировать, что список будет отсортирован, это все же лучший способ получить индекс элемента?

Будет ли бинарный поиск быстрее возвращать индекс? Кроме того, есть ли способ заставить стандартную библиотеку python выполнять бинарный поиск по индексу элемента в списке?

0

python search time indexing

Источник

Adi 23 июл '16 в 23:56

1 ответ

Решение

Другие вопросы по тегам python search time indexing

Olathe 24 июл '16 в 00:07 2016-07-24 00:07 · Accepted Answer · 2016-07-24 00:07

Да, бинарный поиск, как правило, будет быстрее. Нет, стандартная библиотека 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