A maneira mais rápida de indexar um elemento em uma lista classificada em python? [fechadas]

Question

As listas do Python têm uma função list.index(elem) que, pelo que sei, é executada em tempo O (n). No entanto, se eu puder garantir que a lista seja classificada, essa ainda é a melhor maneira de obter o índice de um elemento?

Uma pesquisa binária retornará o índice mais rapidamente? Além disso, existe uma maneira de forçar a biblioteca padrão do Python para fazer uma pesquisa binária para o índice de um elemento em uma lista?

    

Answer 1

Sim, uma pesquisa binária geralmente será mais rápida. Não, a biblioteca padrão index function não tem opção para isso.

Outra resposta tem código para uma pesquisa binária:

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