Buscar em sequências ordenadas com bisect

Em uma lista de números em ordem crescente, o elemento central divide os candidatos em duas regiões previsíveis. Ao comparar o alvo com esse elemento, uma das metades pode ser descartada com segurança.

Exemplo: se o alvo é menor que o valor central, tudo que está à direita dele também é grande demais. Se o alvo é maior, os valores à esquerda são pequenos demais. A busca continua apenas no intervalo que ainda pode conter a posição procurada.

O alvo 18 é menor que o valor central 21. Por isso, 21 e todos os valores à direita saem da busca; somente a região à esquerda permanece candidata.

Esse descarte só é válido se a sequência já estiver ordenada pelo mesmo critério usado na comparação. Neste tutorial, usaremos listas numéricas em ordem crescente, como [3, 8, 12, 17, 21].

O módulo bisect trabalha sobre essa condição: ele não ordena a lista e não verifica se ela realmente está ordenada. Em uma lista fora de ordem, o resultado pode não representar a posição esperada.

Importe as funções do módulo padrão bisect:

from bisect import bisect_left, bisect_right

Em uma lista numérica ordenada:

• bisect_left(lista, alvo) devolve o espaço antes do primeiro valor igual ao alvo. À esquerda ficam valores menores; à direita, valores maiores ou iguais.
• bisect_right(lista, alvo) devolve o espaço depois do último valor igual ao alvo. À esquerda ficam valores menores ou iguais; à direita, valores maiores.

As duas funções retornam uma posição de inserção; elas não alteram a lista.

Considere idades = [18, 21, 21, 21, 30] e alvo 21.

As posições podem coincidir quando não há um valor equivalente.

bisect_left(valores, alvo) retorna a primeira posição onde o alvo poderia ficar. Isso ainda não prova que ele está na lista.

Para confirmar a presença, use duas condições:

1. a posição deve existir na lista (posicao < len(valores));
2. o elemento nessa posição deve ser igual ao alvo (valores[posicao] == alvo).

A mesma posição candidata pode apontar para uma ocorrência real ou apenas para o local de inserção.

A ordem das condições evita acessar um índice inexistente.

Em uma lista ordenada, todas as ocorrências de um mesmo valor ficam juntas. Para o alvo 8, bisect_left encontra o início desse bloco e bisect_right encontra a posição logo após seu fim.

Assim, se esquerda = bisect_left(valores, 8) e direita = bisect_right(valores, 8), a quantidade de ocorrências é direita - esquerda. Não é preciso criar uma fatia apenas para contar.

Os marcadores mostram as posições de inserção que envolvem todas as ocorrências de 8.

A diferença entre os limites é a contagem.

Para devolver valores entre minimo e maximo, os limites dependem do contrato:

• minimo <= valor <= maximo: use bisect_left no mínimo e bisect_right no máximo.
• minimo <= valor < maximo: use bisect_left nos dois extremos.

A fatia sempre exclui seu índice final. O uso de bisect_right no máximo inclusivo faz a fatia terminar depois das ocorrências desse máximo.

Além de localizar limites, o módulo bisect oferece insort_left e insort_right. Elas encontram a posição adequada e inserem o valor na própria lista; o retorno é None.

Use insort_left para inserir antes dos valores equivalentes e insort_right para inserir depois deles. As duas preservam a ordem crescente, desde que a lista já esteja ordenada pelo mesmo critério.

As duas variantes diferem apenas no ponto escolhido dentro de um bloco de valores iguais.

Execute o exemplo e observe que a lista é alterada após cada chamada.

A busca binária usada para encontrar o limite custa O(log n). Porém, uma lista é contígua: para abrir espaço no meio ou no início, os elementos à direita precisam ser deslocados.

Por isso, insort_left e insort_right têm custo O(n) no pior caso. A etapa de busca é rápida, mas o deslocamento pode envolver quase toda a lista.

Inserir 4 antes de 5 exige mover 5, 7 e 9 uma posição para a direita.

O custo de bisect só descreve a localização de um limite em uma sequência que já está ordenada. Se os dados chegam sem ordem, inclua a preparação no cenário.

duracoes_ordenadas = sorted(duracoes)

Para n elementos, sorted custa O(n log n) no pior caso. Como ela cria uma nova lista, também requer O(n) de armazenamento adicional para essa lista ordenada.

A ordenação é uma etapa anterior às consultas, não um detalhe gratuito da busca.

Sem atualizações e sem criar fatias, m consultas de limites em uma lista preparada custam:

O(n log n + m log n)

O primeiro termo é a ordenação inicial; o segundo reúne as m localizações com bisect. Se a lista já chega ordenada pelo critério correto, o termo de preparação não entra nessa operação.

insort_left e insort_right encontram a posição em O(log n), mas inserir em uma lista pode deslocar elementos à direita. No pior caso, cada inserção custa O(n).

Portanto, muitas inserções acumulam custos de deslocamento. Manter a lista ordenada não torna as atualizações automaticamente logarítmicas.

Não existe uma estrutura sempre mais rápida. Primeiro preserve o contrato da consulta: você precisa apenas saber se um valor existe, obter um registro por chave, localizar sua posição ordenada ou trazer todos os valores de uma faixa?

Depois considere a carga completa: preparação, memória extra, quantidade de consultas, atualizações e tamanho dos resultados devolvidos.

Neste exemplo, as durações são preparadas uma vez com sorted. As consultas usam limites binários; só a faixa solicitada é materializada como uma nova lista. Copie o script para um arquivo .py no seu computador e execute-o.

Dados, consultas, verificações e atualização em um único arquivo.

A consulta de faixa encontra dois índices; a fatia usa o início inclusivo e o fim exclusivo.

bisect_left produz uma posição onde o alvo poderia começar, não uma prova de presença. Por isso presente confirma duas condições: a posição existe na lista e o elemento nessa posição é igual ao alvo. Já contar não cria uma fatia: calcula somente direita - esquerda.