Busca binária e suas variações: lower/upper bound, array rotacionado, busca na resposta

1. Visão geral

Busca binária é um algoritmo de busca em dados já ordenados com complexidade O(log n). A ideia é bem simples, mas a implementação é propensa a erros: loop infinito, erro off-by-one, overflow ao calcular mid.

Este artigo vai da versão básica até as variações mais comuns: encontrar a primeira/última posição de um elemento duplicado, contar ocorrências, buscar em array rotacionado e busca binária na resposta. Ao fim, você terá um conjunto de templates de implementação com menos erros, acompanhados de testes para validar.

2. Busca binária básica

Suponha que você tenha um array de preços de produtos já ordenado em ordem crescente e precisa encontrar a posição de um determinado preço:

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

Explicação:

• lo e hi formam um intervalo fechado [lo, hi]. Esta é a região onde target pode estar.
• A condição lo <= hi significa que o loop continua enquanto o intervalo tem pelo menos um elemento.
• mid = lo + (hi - lo) / 2 evita overflow. A forma (lo + hi) / 2 causaria overflow quando lo + hi exceder Integer.MAX_VALUE. Uma forma equivalente é (lo + hi) >>> 1.
• A cada passo, eliminamos mid do intervalo (mid + 1 ou mid - 1), então o intervalo sempre se reduz e o loop é garantido terminar.

Resultado:

3
-1

Esta versão é suficiente quando o array não tem elementos duplicados e você só precisa saber “tem ou não tem”. Com elementos duplicados, ela retorna uma posição arbitrária dentro do grupo. Geralmente, isso não é o que você quer.

3. Lower bound e upper bound

As duas variações mais importantes são:

• lower bound: o primeiro índice onde a[i] >= target.
• upper bound: o primeiro índice onde a[i] > target.

Ambas sempre retornam um índice em [0, n], mesmo quando target não está no array. Este índice é exatamente a posição de inserção para manter o array ordenado.

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // intervalo semi-aberto [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Diferenças em relação à versão básica:

• Usamos um intervalo semi-aberto [lo, hi), então hi é inicializado com a.length e a condição do loop é lo < hi.
• Quando a[mid] satisfaz a condição “já é grande o suficiente”, atribuímos hi = mid em vez de mid - 1, porque mid ainda pode ser a resposta.
• As duas funções diferem apenas no operador < e <=.

Testando com um array com elementos duplicados:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

Com 300, o resultado 4 indica que se inserirmos 300 ele fica antes de 350. Com 900, o resultado é igual a n, significando que todos os elementos são menores.

3.1. Primeira posição, última posição e contagem de ocorrências

A partir dessas duas funções, você deduz imediatamente problemas familiares:

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

Com prices acima e target = 200, obtemos firstIndexOf = 1, lastIndexOf = 3, count = 3. Ponto importante: sempre verifique os limites i < a.length (ou i >= 0) antes de acessar a[i].

3.2. Contagem de elementos em um intervalo

Uma aplicação prática é contar o número de pedidos com valor em [min, max]:

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

Com {100, 200, 200, 200, 350, 500} e intervalo [150, 400], o resultado é 6 - ... ? Vamos calcular: upperBound(400) = 5, lowerBound(150) = 1, então o resultado é 4. Cada consulta custa apenas O(log n), sem precisar varrer todo o array.

4. Busca em array rotacionado

Um array rotacionado é um array já ordenado que foi “cortado” em um ponto e suas duas metades foram trocadas, como em {40, 50, 60, 10, 20, 30}. Este array não está mais inteiramente em ordem crescente, mas pelo menos uma metade em torno de mid ainda está ordenada. Usamos isso para decidir para qual lado ir:

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // metade esquerda está ordenada
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // metade direita está ordenada
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Explicação:

• a[lo] <= a[mid] indica que o intervalo [lo, mid] está em ordem crescente. Se target está no intervalo de valores dessa metade, reduzimos para a esquerda. Caso contrário, vamos para a direita.
• No outro caso, o intervalo [mid, hi] está em ordem crescente e aplicamos raciocínio simétrico.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

Observação: Esta implementação assume que o array não tem elementos duplicados. Com um array como {2, 2, 2, 3, 2}, a condição a[lo] <= a[mid] não consegue mais distinguir qual metade está ordenada. Nesse caso, você precisa lidar adicionalmente com a[lo] == a[mid] incrementando lo, e a complexidade de pior caso torna-se O(n).

5. Busca binária na resposta

Esta é a variação mais poderosa. Ela não busca em um array, mas encontra o menor valor que satisfaz uma condição. A única condição para aplicar é que o predicado deve ser monótono: se x satisfaz, então todo valor maior que x também satisfaz. Em outras palavras, a sequência de resultados tem a forma false, false, ..., true, true.

Escrevemos uma função genérica:

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** O menor valor em [lo, hi] para o qual ok retorna true. Assume-se que ok(hi) == true. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Esta função tem a mesma estrutura de lowerBound. Na verdade, lowerBound é apenas um caso especial com o predicado a[i] >= target.

Aplicando a um problema real: um depósito tem uma lista de pacotes em ordem fixa, precisa entregar todos em maxDays dias. A cada dia, o caminhão leva pacotes consecutivos, com o peso total não excedendo a capacidade. Qual é a menor capacidade necessária?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

Explicação:

• lo é o pacote mais pesado, pois o caminhão deve conseguir levar pelo menos qualquer pacote. hi é o peso total, pois nesse caso só é necessário um dia. Portanto, ok(hi) é certamente verdadeiro.
• canShip simula uma estratégia gulosa: coloca pacotes no caminhão até que ficar sobrecarregado, depois vai para o próximo dia. Quanto maior a capacidade, menos dias necessários, logo o predicado é monótono.
• O custo total é O(n · log(sum)), em vez de tentar cada capacidade.

6

Com capacidade 6, o cronograma é [3, 2], [2, 4], [1, 4], exatamente 3 dias. Com 5, precisamos de 4 dias, então 5 não funciona.

Com esse padrão você consegue resolver muitos outros problemas: número mínimo de threads para processar um batch a tempo, menor limite de taxa, raiz quadrada inteira de um número.

6. Usando a biblioteca padrão do Java

Java já fornece Arrays.binarySearch e Collections.binarySearch. Você precisa entender bem o valor retornado por elas:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• Quando encontra, a função retorna o índice do elemento.
• Quando não encontra, ela retorna -(insertionPoint) - 1. Aqui a posição de inserção é 4, então o resultado é -5. Para recuperar a posição, calcule -(result) - 1.
• Com elementos duplicados, a documentação não garante qual posição no grupo será retornada. Se precisar da primeira ou última posição, use seu próprio lowerBound/upperBound.

Com listas de objetos, você passa um Comparator que corresponde à ordem já usada:

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

Observação: Collections.binarySearch em LinkedList não alcança O(log n) porque o acesso por índice custa O(n). Use ArrayList ou array.

7. Testes

Adicione as dependências JUnit 5 e AssertJ. Se o projeto usa spring-boot-starter-test, ambas já estão incluídas.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

Escreva testes para casos extremos. É aqui que a busca binária mais falha:

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

O teste lowerBoundMatchesLinearScan compara com a contagem linear em 1.000 arrays aleatórios, incluindo array vazio. Este tipo de teste de comparação captura erros off-by-one muito melhor que alguns exemplos escritos à mão.

8. Erros comuns e quando não usar

Erros comuns:

• Misturar duas convenções de intervalo. Você inicializa hi = n (semi-aberto) mas depois faz loop com while (lo <= hi) e atribui hi = mid - 1. O resultado é ler fora do array. Escolha uma convenção e mantenha-a consistente.
• Loop infinito. Se você escreve lo = mid junto com mid = (lo + hi) / 2, quando hi = lo + 1 teremos mid == lo e o intervalo não se reduz. Se realmente precisar de lo = mid, arredonde para cima: mid = lo + (hi - lo + 1) / 2.
• Overflow ao calcular mid ou ao somar em busca binária na resposta. Use long para valores que podem ficar grandes.
• Predicado não-monótono. Busca binária ainda retorna um número, mas ele é sem sentido. Prove a monotonicidade antes de aplicar.

Quando não usar busca binária:

• Dados não-ordenados e busca apenas algumas vezes. Ordenar custa O(n log n), procura linear é apenas O(n).
• Você só precisa checar “tem ou não tem” com muitas buscas. Nesse caso HashSet oferece O(1) em média.
• Dados mudam continuamente, com inserções e remoções frequentes. Manter o array ordenado custa O(n) por inserção. Considere TreeMap/TreeSet, que têm ceilingKey, floorKey, higherKey equivalentes a lower bound e upper bound.
• Array muito pequeno, apenas dezenas de elementos. Varredura linear é frequentemente tão rápida ou mais rápida por causa do cache, e o código é mais simples.

9. Conclusão

Busca binária não é apenas “encontrar um elemento em um array”. Quando você domina lower bound e upper bound com intervalo semi-aberto [lo, hi), consegue resolver problemas de primeira/última posição, contagem de elementos e contagem por intervalo em poucas linhas. Array rotacionado exige um passo extra para determinar qual metade está ordenada. Busca binária na resposta estende a técnica para qualquer problema com predicado monótono.

Mantenha uma única convenção de intervalo, use >>> ou lo + (hi - lo) / 2 para evitar overflow, e sempre tenha testes que comparem com busca linear. Esses três hábitos eliminam quase todos os erros pelos quais busca binária é famosa por cometer.