Manter uma lista em ordem parece simples: adicione o novo item e chame sort(). Essa abordagem funciona para conjuntos pequenos ou atualizações raras, mas repete trabalho quando o programa recebe valores continuamente e precisa consultar faixas, limites ou posições de inserção. O módulo bisect no Python resolve esse cenário com busca binária. Ele encontra rapidamente o ponto correto em uma sequência já ordenada e permite inserir novos elementos sem procurar a posição por varredura linear.
Neste guia, você aprenderá a diferença entre bisect_left() e bisect_right(), como usar insort(), como pesquisar registros com key, quando pré-calcular chaves e quais limites de desempenho considerar. O assunto complementa os artigos sobre ordenação com sort e sorted, listas em Python, funções em Python, estruturas do módulo collections e análise de desempenho com cProfile.
O que é o módulo bisect?
O módulo bisect implementa o algoritmo de bisseção para localizar posições em listas ordenadas. Em vez de comparar o valor procurado com todos os elementos, a busca verifica o centro da faixa, elimina metade das possibilidades e repete o processo. Por isso, localizar uma posição custa O(log n).
A documentação oficial do bisect destaca uma característica importante: as funções procuram pontos de inserção. Elas não chamam __eq__() para confirmar igualdade; usam comparações de ordem e devolvem um índice entre os elementos. Isso torna a API útil para inserções, consultas de intervalo e pesquisas personalizadas.
A lista precisa estar ordenada
O contrato mais importante é simples: a sequência já deve estar ordenada pelo mesmo critério usado na busca. Se a lista estiver fora de ordem, o índice devolvido pode parecer válido, mas não terá significado confiável.
from bisect import bisect_left
numeros = [3, 8, 12, 19, 25]
indice = bisect_left(numeros, 15)
print(indice) # 3
print(numeros[:indice])
print(numeros[indice:])O resultado indica que o número 15 deveria ser inserido antes do 19, no índice 3. A função não altera a lista. Ela apenas calcula a posição.
bisect_left e bisect_right
A diferença aparece quando o valor já existe. bisect_left() devolve a posição anterior ao primeiro item igual. bisect_right(), também disponível pelo alias bisect(), devolve a posição após o último item igual.
from bisect import bisect_left, bisect_right
valores = [10, 20, 20, 20, 30]
inicio = bisect_left(valores, 20)
fim = bisect_right(valores, 20)
print(inicio) # 1
print(fim) # 4
print(valores[inicio:fim])Essa combinação permite encontrar rapidamente o intervalo ocupado por valores repetidos. A quantidade de ocorrências é fim - inicio. O mesmo padrão funciona com datas, pontuações, preços e outras chaves ordenáveis.
Como procurar um valor exato
Como bisect_left() retorna um ponto de inserção mesmo quando o valor não existe, verifique o índice antes de considerar a busca bem-sucedida:
from bisect import bisect_left
def encontrar_indice(valores, procurado):
indice = bisect_left(valores, procurado)
if indice != len(valores) and valores[indice] == procurado:
return indice
raise ValueError(f"{procurado!r} não encontrado")
print(encontrar_indice([2, 5, 9, 14], 9))Para várias consultas exatas por chave, um dicionário costuma ser mais apropriado. O bisect se destaca quando você precisa localizar limites, vizinhos ou posições em uma faixa ordenada.
Inserindo com insort
insort_left() e insort_right() combinam a busca da posição com list.insert(). A primeira coloca o novo valor antes dos iguais; a segunda coloca depois.
from bisect import insort
fila = [4, 9, 15, 22]
insort(fila, 12)
insort(fila, 9)
print(fila)Usar append() quebraria a ordenação quando o valor não fosse maior que o último item. Ordenar toda a lista após cada inserção também funcionaria, porém faria mais trabalho do que localizar diretamente o ponto adequado.
O custo real da inserção
A busca binária custa O(log n), mas inserir no meio de uma lista custa O(n), pois os elementos seguintes precisam ser deslocados. Portanto, insort() é conveniente e eficiente para consultas frequentes com um volume moderado de inserções, mas não transforma a lista em uma estrutura de inserção logarítmica.
Quando há milhões de atualizações, considere uma árvore balanceada, banco de dados indexado ou biblioteca de coleções ordenadas. Quando o programa só adiciona valores no final em ordem crescente, append() continua sendo a opção mais simples e rápida. A documentação oficial sobre estruturas de dados ajuda a comparar operações comuns de listas, filas e outras coleções.
Limitando a busca com lo e hi
Os parâmetros lo e hi restringem a pesquisa a uma parte da lista. Isso é útil quando outra etapa já delimitou uma região relevante.
from bisect import bisect_left
dados = [2, 5, 8, 11, 14, 17, 20]
indice = bisect_left(dados, 13, lo=2, hi=6)
print(indice)Os limites seguem a convenção de fatias: lo é incluído e hi é excluído. Passe índices coerentes com a ordenação e evite usar esses parâmetros apenas como micro-otimização sem medição.
Pesquisando objetos com key
Desde o Python 3.10, as funções aceitam o argumento key. Ele extrai a chave de comparação de cada elemento armazenado. Na busca, a função não é aplicada ao valor x; você fornece diretamente a chave procurada.
from bisect import bisect_left
from operator import itemgetter
produtos = [
{"nome": "Caderno", "preco": 18.0},
{"nome": "Mouse", "preco": 65.0},
{"nome": "Teclado", "preco": 120.0},
]
por_preco = itemgetter("preco")
indice = bisect_left(produtos, 70.0, key=por_preco)
print(produtos[indice]["nome"])Os registros precisam estar ordenados pela mesma função key. Caso contrário, a pesquisa estará usando um critério diferente daquele que organizou a lista.
Inserindo registros com key
Nas funções insort, a chave é aplicada ao item novo durante a etapa de pesquisa, mas o objeto completo é inserido na lista.
from bisect import insort
from operator import itemgetter
tarefas = [
{"prioridade": 1, "titulo": "Restaurar serviço"},
{"prioridade": 3, "titulo": "Gerar relatório"},
]
nova = {"prioridade": 2, "titulo": "Responder cliente"}
insort(tarefas, nova, key=itemgetter("prioridade"))
print([t["prioridade"] for t in tarefas])Para empates, escolha conscientemente entre insort_left e insort_right. Se a ordem de chegada precisar ser estável, inclua um contador crescente na chave ou no registro.
Pré-calculando chaves
As funções de busca são sem estado e não armazenam resultados da função key. Em um loop, a mesma chave pode ser calculada repetidamente. Se a extração for cara, mantenha uma lista paralela de chaves.
from bisect import bisect_left
clientes = [
("Ana", 1200),
("Bruno", 2500),
("Carla", 4100),
]
saldos = [cliente[1] for cliente in clientes]
indice = bisect_left(saldos, 3000)
print(clientes[indice])Ao inserir ou remover registros, atualize as duas listas na mesma operação. Outra opção indicada pela documentação é aplicar functools.cache() quando a função de chave recebe valores reutilizáveis e puros.
Consultas por faixa
Uma aplicação frequente é selecionar todos os valores entre dois limites. Use bisect_left() no limite inferior e bisect_right() no superior:
from bisect import bisect_left, bisect_right
temperaturas = [12, 15, 18, 18, 21, 24, 27, 30]
inicio = bisect_left(temperaturas, 18)
fim = bisect_right(temperaturas, 24)
print(temperaturas[inicio:fim])A busca dos dois limites custa O(log n). Criar a fatia custa tempo proporcional à quantidade de itens devolvidos. Quando você só precisa contar, use fim - inicio e evite copiar os elementos.
Classificando valores por intervalos
bisect() também pode transformar limites ordenados em categorias. O índice retornado seleciona a faixa correspondente.
from bisect import bisect
limites = [60, 70, 80, 90]
conceitos = "FDCBA"
def conceito(nota):
return conceitos[bisect(limites, nota)]
print(conceito(77))
print(conceito(90))O padrão serve para faixas de imposto, níveis de risco, tamanhos de pacote e regras de preço. Documente claramente se o limite pertence à faixa anterior ou posterior, pois essa decisão determina o uso de bisect_left ou bisect_right.
Encontrando vizinhos
O índice de inserção permite encontrar o valor imediatamente menor ou maior. Após bisect_left(valores, x), o item em indice - 1 é o maior valor menor que x, quando o índice é maior que zero. O item no próprio índice é o primeiro maior ou igual, quando o índice ainda está dentro da lista.
from bisect import bisect_left
horarios = [8, 10, 13, 16, 19]
indice = bisect_left(horarios, 14)
anterior = horarios[indice - 1] if indice else None
proximo = horarios[indice] if indice != len(horarios) else None
print(anterior, proximo)Esse padrão é útil para calendários, séries temporais, versões e pontos de medição.
bisect, dicionário, set ou heap?
Use bisect quando a ordem é importante e você precisa de limites, vizinhos ou faixas. Use dicionário ou set para localizar valores exatos com alta frequência. Use heapq quando precisa retirar repetidamente o menor ou maior elemento, mas não necessita pesquisar posições arbitrárias.
Um banco de dados com índice é mais apropriado quando os dados não cabem em memória, precisam de persistência ou recebem atualizações concorrentes. A estrutura correta depende do padrão de leitura e escrita, não apenas da complexidade da busca isolada.
Segurança em múltiplas threads
As funções do módulo não são seguras para alterações concorrentes na mesma sequência. Se uma thread modificar a lista enquanto outra executa a busca ou inserção, a ordenação pode ser corrompida e o comportamento fica indefinido. Proteja a operação completa com um bloqueio ou mantenha estruturas separadas por thread.
Não basta bloquear somente bisect() e liberar antes de insert(). Outra thread poderia alterar a lista entre as duas etapas. O cálculo da posição e a inserção precisam formar uma seção crítica única.
Erros comuns
- Aplicar
bisecta uma lista que não está ordenada. - Ordenar por uma chave e pesquisar usando outra.
- Interpretar o índice retornado como confirmação de que o valor existe.
- Ignorar a diferença entre inserção à esquerda e à direita.
- Esperar inserções
O(log n)em uma lista comum. - Recalcular uma função
keycara em milhares de buscas. - Modificar a lista concorrentemente sem sincronização.
Como testar
Teste as bordas: lista vazia, valor menor que todos, maior que todos, duplicatas e limites exatos. Verifique também se a lista continua ordenada após uma sequência de inserções.
from bisect import insort
def test_insercoes_preservam_ordem():
valores = []
for numero in [9, 2, 7, 7, 1]:
insort(valores, numero)
assert valores == [1, 2, 7, 7, 9]Para funções de faixa, inclua casos sem resultados e casos em que todos os itens pertencem ao intervalo. Isso evita erros de índices e decisões incorretas sobre limites inclusivos.
Boas práticas
- Centralize pesquisas e inserções em funções pequenas.
- Documente o critério de ordenação e o tratamento de duplicatas.
- Use
keyconsistente com a ordenação inicial. - Pré-calcule chaves quando a extração for cara.
- Evite copiar fatias quando só precisa contar elementos.
- Meça inserções grandes antes de escolher uma lista.
- Proteja a operação completa quando houver concorrência.
Conclusão
O bisect no Python transforma listas ordenadas em estruturas eficientes para localizar pontos de inserção, limites e vizinhos. bisect_left e bisect_right controlam o tratamento de duplicatas, enquanto insort mantém a ordem após novas entradas. O argumento key amplia a técnica para dicionários, tuplas e objetos.
A busca é logarítmica, mas a inserção em listas continua linear. Por isso, o módulo é excelente para muitas leituras e um número moderado de atualizações. Quando o volume, a concorrência ou a persistência crescem, outra estrutura pode ser melhor. Com o contrato de ordenação bem definido e testes de borda, bisect oferece uma solução simples, previsível e poderosa.
