Busca binária em lista em Python

Página Inicial / ∣V∣+∣E∣ (Gráfico) / Busca binária em lista em Python
É possível usar o método bisect.bisect_left da biblioteca padrão para fazer consultas, e podemos observar que a diferença é considerável. Observe o código que testa a busca binária vs busca linear em uma lista de apenas 1000 elementos:
import timeit

setup = """
from bisect import bisect_left
from itertools import islice
import random

def sample(n, N):
    for i in range(N):
        if random.randrange(N - i) < n:
            yield i
            n -= 1
            if n <= 0:
                break

random.seed(42)
l = list(sample(1000, 1000000))

# last element in list
s = 998707
# last element in list+1
ns = 998708
"""
print("Busca binária, último elemento", timeit.timeit('''
i = bisect_left(l, s)
if i < len(l) and l[i] == s: pass
''', setup=setup, number=10000))
print("Busca binária, elemento fora", timeit.timeit('''
i = bisect_left(l, ns)
if i < len(l) and l[i] == ns: pass
''', setup=setup, number=10000))
print("Busca linear, elemento fora", timeit.timeit("ns in l", setup=setup, number=10000))
print("Busca linear, último elemento", timeit.timeit("s in l", setup=setup, number=10000))
Na minha máquina ele retorna os seguintes resultados:
Busca binária, último elemento 0.002540202000091085
Busca binária, elemento fora 0.002100026000334765
Busca linear, elemento fora 0.07512355499966361
Busca linear, último elemento 0.07665298000028997
Se aumentarmos o número de elementos do vetor para 100000 (primeiro argumento de sample), a diferença fica mais explícita:
Busca binária, último elemento 0.0033003730004566023
Busca binária, elemento fora 0.003177442999003688
Busca linear, elemento fora 7.521412267000414
Busca linear, último elemento 7.655833986998914
Então se a sua lista estiver ordenada, é sempre recomendado usar bisect_left em Python.