O módulo bisect da biblioteca padrão resolve um problema comum: localizar rapidamente a posição correta de um valor em uma lista já ordenada. Em vez de percorrer todos os elementos, ele aplica busca binária e reduz o número de comparações. Isso é útil em rankings, faixas de preço, tabelas de pontuação, agendas, filas priorizadas e sistemas que mantêm dados em ordem sem depender de bibliotecas externas.
Neste guia, você aprenderá como usar bisect_left, bisect_right, insort_left e insort_right, quando cada função faz sentido, quais são os custos reais e como evitar erros de modelagem.
Por que usar busca binária
Em uma lista comum, procurar um item pode exigir verificar muitos elementos. Em uma lista ordenada, a busca binária compara o valor com o centro da sequência e descarta metade do espaço a cada passo. O custo de localizar a posição é logarítmico, embora inserir em uma lista continue sendo linear porque os elementos seguintes precisam ser deslocados.
Isso significa que bisect é excelente quando há muitas consultas e poucas inserções. Em cargas com inserções intensas, uma árvore balanceada, um banco de dados ou outra estrutura pode ser mais adequada.
bisect_left e bisect_right
from bisect import bisect_left, bisect_right
valores = [10, 20, 20, 20, 30, 40]
inicio = bisect_left(valores, 20)
fim = bisect_right(valores, 20)
print(inicio) # 1
print(fim) # 4
print(valores[inicio:fim]) # [20, 20, 20]
bisect_left retorna a primeira posição válida para o item. bisect_right retorna a posição logo após os valores iguais. Essa diferença permite contar duplicatas, criar intervalos e escolher se um novo item deve ficar antes ou depois dos equivalentes.
Inserindo sem perder a ordem
from bisect import insort_left, insort_right
notas = [5.0, 6.5, 8.0, 9.5]
insort_left(notas, 8.0)
insort_right(notas, 8.0)
print(notas)
As funções insort localizam a posição e executam a inserção. O código fica mais claro do que uma busca manual seguida de list.insert. Ainda assim, o deslocamento dos elementos torna a operação linear.
Buscando valores exatos
from bisect import bisect_left
def encontrar_exato(lista, alvo):
pos = bisect_left(lista, alvo)
if pos != len(lista) and lista[pos] == alvo:
return pos
return -1
É importante verificar o índice retornado. bisect_left informa onde o valor deveria estar, mas isso não garante que ele exista. Sem a validação, o código pode aceitar um item diferente ou acessar uma posição fora da lista.
Criando faixas
from bisect import bisect_right
limites = [18, 30, 45, 60]
rotulos = ["iniciante", "júnior", "pleno", "sênior", "especialista"]
def classificar(idade):
return rotulos[bisect_right(limites, idade)]
Esse padrão transforma limites ordenados em classificações rápidas. Ele pode ser usado em cálculo de frete, tributação, níveis de serviço, faixas de latência, classificação de notas e regras de desconto.
Usando key em versões modernas do Python
As funções de busca aceitam o parâmetro key para extrair a chave dos elementos. A chave não é aplicada ao valor procurado; por isso, passe ao argumento x uma chave compatível.
from bisect import bisect_left
produtos = [
{"nome": "A", "preco": 10},
{"nome": "B", "preco": 25},
{"nome": "C", "preco": 40},
]
pos = bisect_left(produtos, 30, key=lambda item: item["preco"])
print(pos) # 2
Em buscas repetidas, a função de chave pode ser chamada muitas vezes. Para chaves caras, considere manter uma lista paralela já calculada ou aplicar cache.
Lista paralela de chaves
from bisect import bisect_left
registros = [
{"id": 101, "nome": "Ana"},
{"id": 205, "nome": "Bruno"},
{"id": 330, "nome": "Carla"},
]
ids = [item["id"] for item in registros]
pos = bisect_left(ids, 205)
if pos < len(ids) and ids[pos] == 205:
print(registros[pos])
Esse desenho evita recalcular a chave. O cuidado é manter as duas listas sincronizadas em toda inserção, remoção ou atualização.
Erros comuns
O primeiro erro é usar bisect em uma lista não ordenada. A função não valida a ordenação e pode retornar posições aparentemente plausíveis, porém incorretas. O segundo é esquecer que inserir no meio da lista custa tempo linear. O terceiro é confundir a posição de inserção com a confirmação de existência. O quarto é misturar critérios: se a lista foi ordenada por preço, a busca também deve usar preço.
Outro problema aparece em concorrência. Operações compostas de busca e inserção não devem ser tratadas como atômicas quando várias threads ou processos alteram a mesma coleção. Proteja a estrutura com sincronização adequada ou use um armazenamento transacional.
Quando usar e quando evitar
Use bisect em tabelas pequenas ou médias mantidas em memória, configurações estáticas, intervalos ordenados, catálogos com muitas leituras e poucas alterações. Evite-o como substituto de índice de banco de dados em grandes volumes mutáveis, em filas de prioridade com muitas remoções ou em estruturas compartilhadas sem controle de concorrência.
Exemplo completo: ranking ordenado
from bisect import bisect_right
ranking = []
pontos = []
def adicionar(nome, pontuacao):
pos = bisect_right(pontos, pontuacao)
pontos.insert(pos, pontuacao)
ranking.insert(pos, {"nome": nome, "pontos": pontuacao})
def acima_de(minimo):
pos = bisect_left(pontos, minimo)
return ranking[pos:]
O exemplo mantém duas listas sincronizadas e permite localizar rapidamente o início de uma faixa. Em aplicações reais, encapsule essas listas em uma classe e teste todas as operações para impedir divergências.
Boas práticas
Documente o critério de ordenação, valide entradas, escreva testes com duplicatas e limites vazios, meça o custo de inserções e encapsule a estrutura. Para aprender mais sobre coleções e organização de dados, consulte os guias sobre difflib, fractions, statistics, types e linecache.
As referências oficiais são a documentação do bisect e a documentação de estruturas de dados.
Conclusão
bisect oferece uma solução pequena, eficiente e previsível para pesquisar posições em listas ordenadas. O ganho principal está nas consultas logarítmicas e na clareza do código. Quando o padrão de acesso combina muitas leituras com poucas inserções, ele costuma ser uma escolha excelente. Quando a coleção cresce ou muda constantemente, use as mesmas medições para decidir se é hora de migrar para uma estrutura especializada.
