bisect_left e bisect_right
Encontre pontos de inserção em uma lista ordenada.
bisect_left e bisect_right é uma aula grátis de Competitive Programming Academy 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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