Limite Inferior e Limite Superior
Implemente bisect_left e bisect_right do zero e aplique-os para encontrar as primeiras e últimas posições de um valor-alvo.
Limite Inferior e Limite Superior é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 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.
O que são os limites inferior e superior?
O limite inferior de um valor-alvo em um vetor ordenado é o índice do primeiro elemento maior ou igual ao alvo (geralmente chamado de bisect_left). O limite superior é o índice do primeiro elemento estritamente maior que o alvo (bisect_right). Juntos, eles delimitam todas as ocorrências do alvo e permitem consultas de intervalo em O(log n).
Essas duas operações são a base de muitos problemas de entrevista: contar ocorrências, encontrar intervalos, determinar posições de inserção e muito mais.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Implementando o limite inferior (bisect_left)
bisect_left(arr, x) retorna o índice mais à esquerda i tal que arr[i] >= x, ou len(arr) se todos os elementos forem menores. A implementação usa um limite superior exclusivo: hi = len(arr), condição do laço lo < hi e atualização hi = mid quando arr[mid] >= x. Isso garante que a resposta convirja para a posição válida mais à esquerda.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Implementando o limite superior (bisect_right)
bisect_right(arr, x) retorna o índice mais à esquerda i tal que arr[i] > x. Apenas uma linha difere de bisect_left: a condição muda de arr[mid] < x para arr[mid] <= x. Quando arr[mid] <= x, a resposta está estritamente à direita de mid, então definimos lo = mid + 1; caso contrário, restringimos a busca pela direita.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5Contando ocorrências com os dois limites
Para contar ocorrências de um alvo em um vetor ordenado em O(log n), aplique os dois limites: count = bisect_right(arr, target) - bisect_left(arr, target). Se a contagem for 0, o alvo está ausente. Isso é significativamente mais rápido do que uma varredura linear e é a abordagem padrão para consultas de frequência em dados ordenados.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1Encontrando a primeira e a última posição do alvo
LeetCode 34, 'Encontrar a primeira e a última posição de um elemento em um vetor ordenado', pede que você retorne [first_idx, last_idx] em O(log n). A primeira posição é bisect_left(arr, target) — mas somente se arr[result] == target. A última posição é bisect_right(arr, target) - 1. Se alguma das verificações falhar, retorne [-1, -1].
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]Posição de inserção (LeetCode 35)
LeetCode 35, 'Posição de inserção na busca', pergunta: onde o alvo seria inserido para manter o vetor ordenado? Isso é exatamente bisect_left(arr, target). Se o alvo existir, bisect_left retornará seu índice. Se não existir, bisect_left retornará o índice onde ele seria inserido. Não é necessário nenhum tratamento especial — a mesma função lida com ambas as situações.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)A diferença entre bisect_left e bisect_right
Quando não há duplicados, bisect_left e bisect_right retornam o mesmo índice. A diferença só importa quando o alvo aparece várias vezes. bisect_left aponta para a primeira ocorrência; bisect_right aponta para uma posição após a última ocorrência. Escolha sempre com base no fato de você querer inserir antes das ocorrências existentes (à esquerda) ou depois delas (à direita).
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4Aplicando limites a consultas de frequência em vetores ordenados
Quando precisar responder eficientemente a muitas consultas de frequência por intervalo em um vetor ordenado, pré-calcule o vetor ordenado uma vez e use essas operações de busca binária em cada consulta. Cada consulta responde a quantos elementos estão em [lo, hi]? em O(log n), em vez de O(n). Esse padrão aparece em problemas sobre a contagem de elementos dentro de um intervalo de valores após a ordenação.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)Busca binária por chave personalizada
Às vezes, a chave de busca não é o próprio valor armazenado, mas uma propriedade derivada. O módulo bisect do Python não oferece suporte direto a uma função de chave, mas você pode fazer a busca binária manualmente aplicando a chave dentro do laço. Esse padrão aparece ao buscar em uma lista de objetos por um de seus atributos.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Erros comuns em entrevistas com limites
O erro mais comum é esquecer de validar depois de chamar bisect_left. A função sempre retorna um índice de inserção válido, mas não garante que o elemento nesse índice seja igual ao alvo. Sempre verifique arr[result] == target antes de presumir que o alvo foi encontrado.
Um segundo erro é usar bisect_right quando você quer a primeira ocorrência — bisect_right retorna uma posição após a última ocorrência, portanto subtrair 1 fornece a última, não a primeira.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # FalseResumo: quando usar bisect_left ou bisect_right
Use bisect_left quando precisar de: a primeira ocorrência do alvo, o ponto de inserção que desloca as ocorrências existentes para a direita ou uma verificação de que o alvo existe. Use bisect_right quando precisar de: uma posição após a última ocorrência, o ponto de inserção depois de todas as ocorrências existentes ou a contagem de elementos <= alvo (ela é igual a bisect_right(arr, target)).
Ambas executam em O(log n) e fazem parte da biblioteca padrão do Python, portanto você pode importá-las e usá-las diretamente, a menos que o entrevistador peça que você as implemente do zero.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: bisect_left encontra o primeiro elemento >= alvo, bisect_right encontra o primeiro elemento > alvo (uma posição após a última ocorrência) e a diferença entre eles fornece a contagem de ocorrências em O(log n). A seguir, exploraremos a busca binária no espaço de respostas, em que o espaço de busca é um intervalo de respostas possíveis, não um índice de vetor.
Perguntas Frequentes
A aula “Limite Inferior e Limite Superior” é grátis?
Sim — o texto completo de “Limite Inferior e Limite Superior” é 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 “Limite Inferior e Limite Superior”?
Implemente bisect_left e bisect_right do zero e aplique-os para encontrar as primeiras e últimas posições de um valor-alvo. 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 3 de 4.
Quanto tempo leva a aula “Limite Inferior e Limite Superior”?
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: Esquerda, Direita, Meio
- Busca Binária em Arrays Rotacionados e Não Ordenados
- Limite Inferior e Limite Superior
- Busca Binária no Espaço de Respostas