O módulo bisect usa busca binária para localizar posições em listas ordenadas. Ele permite encontrar o ponto de inserção de um valor sem percorrer todos os elementos e oferece insort() para manter a ordem após a inclusão. É útil em tabelas pequenas ou médias, faixas, rankings, calendários, índices em memória e algoritmos que recebem dados gradualmente.
A busca custa O(log n), mas inserir em uma lista custa O(n), porque elementos posteriores precisam ser deslocados. Portanto, bisect é excelente quando as buscas são frequentes e as inserções moderadas. Para grandes volumes de atualização, árvores, bancos ou estruturas especializadas podem ser mais adequados.
Pré-condição: a lista precisa estar ordenada
As funções não verificam se a sequência já está ordenada.
from bisect import bisect_left
valores = [10, 20, 30, 40]
posicao = bisect_left(valores, 25)
print(posicao)
Se a ordem estiver incorreta ou usar uma regra diferente, o resultado não terá significado confiável.
bisect_left
bisect_left() retorna a posição anterior aos valores iguais.
valores = [10, 20, 20, 20, 30]
print(bisect_left(valores, 20))
É útil para encontrar a primeira ocorrência ou inserir antes de duplicatas.
bisect_right
bisect_right(), também disponível como bisect(), retorna a posição depois dos valores iguais.
from bisect import bisect_right
print(bisect_right(valores, 20))
Use quando novos itens iguais devem ficar depois dos existentes.
Encontre o intervalo de duplicatas
As duas funções delimitam todos os elementos iguais.
inicio = bisect_left(valores, alvo)
fim = bisect_right(valores, alvo)
iguais = valores[inicio:fim]
O slice copia os elementos. Se precisar apenas dos índices, mantenha inicio e fim.
insort_left e insort_right
As funções localizam a posição e inserem na lista.
from bisect import insort_left
insort_left(valores, 25)
A busca é logarítmica, mas o deslocamento da lista continua linear.
Não use append seguido de sort em cada item
Inserir com insort() evita ordenar toda a lista após cada novo elemento.
Entretanto, se muitos elementos já estão disponíveis, geralmente é melhor adicioná-los em lote e ordenar uma única vez.
Busca exata
bisect encontra posições, não oferece uma função direta de busca exata.
def indice_exato(lista, valor):
i = bisect_left(lista, valor)
if i != len(lista) and lista[i] == valor:
return i
raise ValueError("valor não encontrado")
Verifique o índice antes de acessar para evitar IndexError.
Maior valor menor que o alvo
def menor_que(lista, valor):
i = bisect_left(lista, valor)
if i:
return lista[i - 1]
raise ValueError("não existe valor menor")
Variantes semelhantes encontram menor ou igual, maior ou igual e maior estrito.
Faixas numéricas
Uma lista de limites pode classificar valores.
limites = [0, 10, 20, 50]
rotulos = ["negativo", "baixo", "médio", "alto", "muito alto"]
classe = rotulos[bisect_right(limites, numero)]
Teste exatamente nos limites para confirmar a política de inclusão.
Parâmetro key
Versões modernas permitem fornecer uma função key para extrair a chave dos elementos existentes.
registros = [
{"id": 1, "nome": "A"},
{"id": 5, "nome": "B"},
]
posicao = bisect_left(registros, 3, key=lambda item: item["id"])
O valor buscado é comparado com as chaves; ele não passa automaticamente pela mesma função. Leia a assinatura da versão mínima do projeto.
Cache de chaves
Uma key cara pode ser chamada repetidamente durante buscas.
Mantenha uma lista paralela de chaves ou use cache quando os registros forem imutáveis. Atualize ambas as listas de forma atômica.
ids = [item.id for item in registros]
posicao = bisect_left(ids, novo.id)
ids.insert(posicao, novo.id)
registros.insert(posicao, novo)
Tuplas como chave composta
Tuplas já possuem ordem lexicográfica.
eventos = [(10, 1, "a"), (10, 2, "b"), (20, 1, "c")]
posicao = bisect_right(eventos, (10, float("inf"), ""))
Evite incluir payloads não comparáveis depois de campos que podem empatar. Use um contador único.
Datas e horários
Objetos datetime compatíveis podem ser ordenados, mas misturar datas ingênuas e conscientes de timezone gera erro.
Normalize a timezone e defina como tratar eventos com o mesmo instante.
Ranking
Para um ranking crescente, a posição de um valor pode ser obtida com bisect_left(). Para ranking decrescente, use chaves negativas ou mantenha uma regra consistente.
Se atualizações forem muito frequentes, inserir em lista pode se tornar caro.
Percentis aproximados
Uma lista ordenada permite consultar quantis por índice, mas manter todos os valores pode consumir muita memória.
Para streams grandes, considere algoritmos aproximados e estruturas específicas.
Listas imutáveis durante a busca
As funções não são seguras quando outra thread modifica a sequência ao mesmo tempo.
Proteja busca e inserção com o mesmo lock ou use snapshots imutáveis.
Busca e inserção precisam ser atômicas
Calcular uma posição e inserir depois, sem lock, permite que outra operação altere a lista entre as etapas.
with lock:
posicao = bisect_left(valores, novo)
valores.insert(posicao, novo)
insort() simplifica a operação, mas o acesso compartilhado ainda precisa de sincronização.
Comparações e NaN
Valores float('nan') não obedecem a uma ordem total comum, porque comparações são especiais.
Filtre ou normalize NaN antes de manter uma lista ordenada.
Objetos mutáveis
Se uma chave usada para ordenar muda depois da inserção, a lista deixa de estar ordenada.
Remova e reinsira o registro ou use objetos imutáveis para as chaves.
Complexidade real
A busca binária executa poucas comparações, mas inserir desloca referências. Em listas muito grandes, esse deslocamento domina o custo.
Faça benchmarks com a proporção real entre leituras e escritas.
bisect versus heapq
heapq é melhor quando você precisa retirar repetidamente o menor item. bisect é melhor quando precisa de acesso ordenado por índice, faixas e vizinhos.
Consulte heapq no Python.
bisect versus set e dict
Para testar apenas existência, set ou dict normalmente oferecem acesso médio O(1).
Use bisect quando a ordem, a posição ou consultas por intervalo forem importantes.
Persistência
Ao carregar dados de arquivo, valide ou reordene antes das buscas. Não confie que um arquivo externo permaneceu ordenado.
Se a lista for muito grande, um índice em banco de dados pode ser mais apropriado.
Segurança
Limite a quantidade de itens inseridos a partir de fontes externas. Uma lista ordenada ilimitada pode esgotar memória e tornar inserções cada vez mais lentas.
Valide chaves e evite funções de comparação com side effects.
Testes
Teste lista vazia, um elemento, duplicatas, limites, valores menores e maiores que todos, key composta, NaN, atualizações e concorrência.
Verifique a invariante lista == sorted(lista) após sequências de operações.
Erros comuns
Os erros mais frequentes são usar a função em lista não ordenada, confundir left e right, esquecer o custo linear da inserção, alterar chaves no lugar, usar key incorretamente, ignorar NaN e separar busca e inserção sem lock.
Conclusão
bisect oferece busca binária e inserção ordenada com uma API pequena. Ele é ideal para sequências em memória com muitas consultas e quantidade moderada de atualizações.
Escolha corretamente entre left e right, mantenha a mesma regra de ordenação e proteja operações concorrentes. Consulte a documentação oficial de bisect e o artigo de heapq no Python.
