bisect_left e bisect_right
Encontre pontos de inserção em uma lista ordenada.
bisect_left e bisect_right é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Busque sem código repetitivo
O módulo bisect do Python oferece uma busca binária testada para listas ordenadas. Sem um laço escrito manualmente, não há erros de deslocamento de um para corrigir.
import bisectPontos de inserção, não valores booleanos
Em vez de verdadeiro ou falso, bisect retorna um índice onde um valor seria inserido para manter a lista ordenada. Esse índice é o verdadeiro poder.
a = [1, 3, 3, 3, 7]bisect_left favorece a esquerda
bisect_left retorna a primeira posição onde o valor poderia ser inserido. Com duplicatas, ele fica antes de todos os itens iguais, nunca depois deles.
bisect.bisect_left(a, 3) # 1bisect_right favorece a direita
bisect_right retorna a posição imediatamente depois do último item igual. Com duplicatas, ele fica depois de todos os valores correspondentes.
bisect.bisect_right(a, 3) # 4Conte elementos iguais
Subtraia os dois para contar duplicatas de um valor em O(log n). right menos left fornece exatamente quantas vezes ele aparece.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3O valor existia?
Para verificar o pertencimento, obtenha i com bisect_left e confirme que a[i] é igual ao alvo. Primeiro, impeça que i alcance o tamanho da lista.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xPrimeiro elemento maior ou igual a X
bisect_left também encontra o primeiro elemento maior ou igual a x. Esse índice aponta diretamente para a resposta do limite inferior.
i = bisect.bisect_left(a, x) # first >= xPrimeiro elemento estritamente maior
Precisa do primeiro elemento estritamente maior que x? bisect_right fornece esse índice diretamente, como correspondente do limite superior.
i = bisect.bisect_right(a, x) # first > xInsira e mantenha a ordenação
insort encontra o local e insere em uma única chamada, mantendo a lista ordenada. É útil quando você constrói uma estrutura ordenada dinamicamente.
bisect.insort(a, 5) # a stays sortedBusque dentro de uma janela
Os argumentos opcionais lo e hi restringem a busca a uma fatia. Isso evita cópias quando você só precisa de um subintervalo.
bisect.bisect_left(a, x, 2, 5)Chaves por meio de uma lista auxiliar
bisect compara elementos inteiros; portanto, para buscar por um campo, crie uma lista paralela contendo apenas essas chaves e use bisect nela.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Verificação rápida
Raciocine sobre duplicatas e pontos de inserção.
Recapitulação: domínio de bisect
Agora você pode encontrar pontos de inserção, contar duplicatas e localizar limites inferiores e superiores em tempo logarítmico. Recorra a bisect antes de escrever um laço. ✨
Perguntas Frequentes
A aula “bisect_left e bisect_right” é grátis?
Sim — o texto completo de “bisect_left e bisect_right” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “bisect_left e bisect_right”?
Encontre pontos de inserção em uma lista ordenada. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “bisect_left e bisect_right”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Busca Binária Clássica sem Bugs
- bisect_left e bisect_right
- Primeiro True: Busca Binária por Predicado
- Busca Binária na Resposta