O módulo bisect encontra uma posição em uma lista ordenada usando busca binária. Ele é útil para consultas frequentes em sequências pequenas ou médias, mas não transforma uma lista comum em estrutura de inserção barata.
Escolher o lado da inserção
from bisect import bisect_left, bisect_right, insort
notas = [5, 7, 7, 9]
assert bisect_left(notas, 7) == 1
assert bisect_right(notas, 7) == 3
insort(notas, 8)
assert notas == [5, 7, 7, 8, 9]bisect_left aponta antes dos valores iguais; bisect_right aponta depois. Essa escolha importa em intervalos, paginação e regras de desempate. A lista precisa permanecer ordenada pelo mesmo critério.
Buscar objetos por chave
Versões atuais aceitam key para calcular a chave dos itens existentes:
from bisect import bisect_left
produtos = [
{"nome": "Básico", "preco": 50},
{"nome": "Pro", "preco": 120},
]
posicao = bisect_left(produtos, 100, key=lambda item: item["preco"])
assert posicao == 1O valor buscado representa a chave, por isso é 100, não um dicionário. Se a função key for cara e a busca se repetir, mantenha uma lista paralela de chaves ou use cache com cuidado.
Transformar o índice em uma busca de verdade
As funções de bisect retornam um ponto de inserção, não confirmam que o elemento existe. Para localizar uma ocorrência, obtenha o índice e valide o valor antes de acessá-lo:
from bisect import bisect_left
def localizar(valores: list[int], alvo: int) -> int:
indice = bisect_left(valores, alvo)
if indice != len(valores) and valores[indice] == alvo:
return indice
raise ValueError(f"{alvo} não encontrado")A verificação de limite é indispensável porque um alvo maior que todos os itens produz len(valores). A mesma técnica implementa uma busca booleana, o primeiro item maior ou igual ao alvo e outras consultas de limite sem escrever manualmente a busca binária.
bisect_left(lista, x) divide a lista em duas regiões: antes do índice, todos os valores são menores que x; a partir dele, todos são maiores ou iguais. bisect_right() muda as desigualdades para incluir os iguais à esquerda. Pensar nessas garantias reduz erros em intervalos.
Consultar faixas com dois limites
Dois pontos de inserção delimitam rapidamente todos os valores dentro de um intervalo fechado:
from bisect import bisect_left, bisect_right
def entre(valores: list[int], minimo: int, maximo: int) -> list[int]:
inicio = bisect_left(valores, minimo)
fim = bisect_right(valores, maximo)
return valores[inicio:fim]
assert entre([2, 4, 4, 7, 9, 12], 4, 9) == [4, 4, 7, 9]Encontrar os limites custa O(log n), mas criar a fatia custa tempo e memória proporcionais à quantidade retornada. Se só precisar contar elementos, use fim - inicio. Se precisar percorrer sem copiar, itere pelos índices ou use itertools.islice.
A escolha entre limites abertos e fechados fica explícita combinando esquerda e direita. Para [minimo, maximo), use bisect_left nos dois extremos. Para (minimo, maximo], use bisect_right em ambos.
Inserir registros com key
insort_left() e insort_right() também aceitam key. A chave é aplicada aos elementos da lista e ao item inserido durante a busca. Diferentemente de bisect_left() em uma consulta, você passa o registro completo a insort:
from bisect import insort_right
eventos = [
{"instante": 10, "nome": "início"},
{"instante": 20, "nome": "fim"},
]
insort_right(
eventos,
{"instante": 20, "nome": "auditoria"},
key=lambda evento: evento["instante"],
)Com chaves iguais, insort_right coloca o novo item depois dos existentes. Isso não cria estabilidade geral se outros códigos reorganizam a lista. Quando o desempate importa, use uma chave composta, como (instante, sequencia), e mantenha a sequência explicitamente.
O parâmetro key foi adicionado no Python 3.10. Se o projeto suporta uma versão anterior, mantenha uma lista paralela de chaves ou use outra estrutura. Consulte a versão mínima real antes de publicar código de biblioteca.
Entender o custo completo
A busca binária examina aproximadamente log2(n) posições. Porém, uma lista Python é um vetor contíguo de referências. Inserir no meio desloca os elementos seguintes, logo insort é dominado por O(n). Em um fluxo com muitas leituras e poucas inserções, esse custo pode ser uma ótima troca. Em um fluxo com milhares de inserções intermediárias, pode ser o gargalo.
Ordenar uma vez com sorted() costuma ser melhor quando todos os dados chegam em lote. Inserir cada um de n itens com insort pode levar tempo quadrático. Por outro lado, reordenar a lista inteira depois de cada elemento também é desperdício. Avalie o padrão: lote, streaming, proporção de leituras e tamanho máximo.
Para obter repetidamente apenas o menor ou maior item enquanto chegam novos valores, considere heapq. Um heap não mantém todos os itens em ordem para buscas de faixa, mas oferece inserção e remoção da prioridade em O(log n). Para concorrência e persistência, um índice de banco de dados provavelmente fornece garantias melhores.
Evitar chaves recalculadas
Durante a busca, bisect pode chamar key várias vezes e descarta os resultados depois. Se calcular a chave envolve parsing, normalização ou outra operação cara, mantenha uma lista sincronizada:
from bisect import bisect_left
nomes = ["Ana", "Érica", "João"]
chaves = [nome.casefold() for nome in nomes]
novo = "bruno"
indice = bisect_left(chaves, novo.casefold())
chaves.insert(indice, novo.casefold())
nomes.insert(indice, novo)Duas listas exigem atualização atômica do ponto de vista da aplicação. Encapsule as operações em uma classe para impedir que alguém altere somente uma delas. functools.cache pode ajudar quando os mesmos objetos imutáveis são pesquisados várias vezes, mas uma cache sem limite traz seu próprio custo de memória.
Para texto humano, casefold() resolve diferenças simples de caixa, não todas as regras de ordenação linguística. Se a ordem precisa seguir collation de um idioma, use uma ferramenta apropriada e gere consistentemente as chaves.
Mutação, concorrência e invariantes
Alterar um campo usado pela ordenação depois que o objeto entrou na lista quebra a pré-condição silenciosamente. Remova e reinsira o registro, ou use objetos imutáveis. Também não misture tipos que não possuam uma ordem compatível.
As funções do módulo não são thread-safe para uso concorrente sobre a mesma sequência. Se outra thread modificar a lista durante a operação, o resultado pode ficar indefinido e a ordenação pode ser corrompida. Proteja a sequência e todas as operações compostas com a mesma trava, ou concentre as alterações em um único proprietário.
Mesmo em uma thread, “buscar e depois inserir” é uma operação composta. Entre essas etapas, qualquer mutação invalida o índice. insort executa as duas como uma chamada conveniente, mas ainda requer exclusão externa quando há concorrência.
Quando bisect é a escolha adequada
Use bisect quando já existe uma sequência ordenada, as comparações têm uma chave consistente e as consultas superam as inserções. Ele é excelente para tabelas de limites, histórico temporal pequeno, seleção por faixa, cálculo de percentis sobre dados já ordenados e lookup em configurações.
Escreva testes para lista vazia, alvo antes do primeiro e depois do último, duplicatas e limites inclusivos. Teste também a propriedade ordenada após cada operação. Esses casos documentam qual lado dos valores iguais faz parte do contrato.
Uma aplicação comum é converter uma medida contínua em categoria. Mantenha apenas os limites superiores ordenados, use bisect_right e utilize o índice para selecionar o rótulo. Defina explicitamente o comportamento no limite exato e fora da faixa. Essa técnica simplifica tabelas de preço, faixas de pontuação e níveis de alerta.
Para dados imutáveis consultados por muitas requisições, construa e valide a lista uma vez durante a inicialização. Não execute sorted() antes de toda chamada, pois isso transforma uma consulta logarítmica em uma operação dominada por O(n log n). Se dados externos alimentam a tabela, valide monotonicidade e rejeite entradas quebradas com uma mensagem clara.
Não use bisect em um iterador genérico. A busca precisa de acesso aleatório por índice e de comprimento conhecido; uma lista ou outra sequência compatível é necessária. Converter um gerador inteiro em lista pode eliminar a vantagem de memória do streaming. Nesse cenário, repense o algoritmo.
Ao revisar desempenho, meça com tamanhos representativos e inclua a manutenção da estrutura. Um benchmark que cronometra apenas bisect_left ignora deslocamentos, geração de chaves, locks e cópias de fatias, justamente os custos que frequentemente dominam a aplicação.
Compare com o guia de ordenação em Python. Se houver muitas inserções no meio, uma lista pode ser inadequada; banco de dados, heap ou estrutura especializada talvez represente melhor o problema.
A documentação oficial de bisect, consultada em 28 de julho de 2026, detalha pré-condições, key, segurança entre threads e receitas. Meça o fluxo completo, pois a busca custa O(log n), mas a inserção na lista continua O(n).