Limite Inferior e Limite 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.

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.

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.

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.

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].

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.

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).

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.

À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.

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.

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.

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta 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.