Este artigo discute a implementação do algoritmo de busca binária para o problema 704 do Leetcode, que envolve encontrar um valor alvo em um array ordenado de inteiros. A busca binária eficiente requer uma compreensão clara dos intervalos de pesquisa, e duas abordagens comuns são apresentadas: intervalos fechados à esquerda e fechados à direita, e intervalos fechados à esquerda e abertos à direita.

No primeiro caso, com intervalo [esquerda, direita], o loop continua enquanto esquerda <= direita, pois ambos os limites são inclusivos. Quando o elemento médio é maior que o alvo, o limite direito é ajustado para meio - 1, já que o elemento atual não é o alvo e o intervalo à esquerda é pesquisado até essa posição.

O cálculo do índice médio utiliza uma operação de deslocamento para evitar overflow: meio = esquerda + ((direita - esquerda) >> 1), onde >> 1 divide a diferença por dois de forma eficiente.

Para o intervalo fechado à esquerda e aberto à direita [esquerda, direita), o loop usa a condição esquerda < direita, pois o limite direito não é inclusivo. Neste caso, quando o elemento médio excede o alvo, o limite direito é atualizado para meio, mantendo o intervalo de pesquisa sem incluir o elemento atual.

Exemplos de código em Java ilustram ambas as abordagens, com nomes de variáveis e estruturas adaptados para clareza.

Abordagem com intervalo fechado:

class Solucao {
    public int buscar(int[] array, int alvo) {
        if (alvo < array[0] || alvo > array[array.length - 1]) {
            return -1;
        }
        int esquerda = 0, direita = array.length - 1;
        while (esquerda <= direita) {
            int meio = esquerda + ((direita - esquerda) >> 1);
            if (array[meio] == alvo) {
                return meio;
            } else if (array[meio] < alvo) {
                esquerda = meio + 1;
            } else {
                direita = meio - 1;
            }
        }
        return -1;
    }
}

Abordagem com intervalo aberto à direita:

class Solucao {
    public int buscar(int[] array, int alvo) {
        int esquerda = 0, direita = array.length;
        while (esquerda < direita) {
            int meio = esquerda + ((direita - esquerda) >> 1);
            if (array[meio] == alvo) {
                return meio;
            } else if (array[meio] < alvo) {
                esquerda = meio + 1;
            } else {
                direita = meio;
            }
        }
        return -1;
    }
}

A escolha entre as abordagens depende das necessidades específicas, mas o princípio fundamental é manter a consistência do interavlo durante a iteração para garantir a corretude do algoritmo.