Binary Search

Categoria: Searching

O problema

O Linear Search deste repositório responde "isso está aqui?" em O(n) porque não pode presumir nada sobre a ordem dos dados. Se os dados já estiverem ordenados — uma suposição comum e barata, uma vez que tenham sido ordenados uma única vez — esse O(n) está deixando uma quantidade enorme de informação sobre a mesa: cada comparação contra uma coleção desordenada quase não diz nada sobre onde mais procurar; uma comparação contra uma coleção ordenada diz qual metade inteira descartar.

A solução

Comparar o alvo com o elemento do meio. Se corresponder, terminou. Se o alvo for menor, toda a metade superior pode ser descartada — todo elemento ali é garantidamente maior. Se for maior, descarta-se a metade inferior. Repete-se no que sobrar. Cada comparação elimina metade dos candidatos restantes, o que é o que torna isso O(log n): o espaço de busca encolhe geometricamente, não linearmente. Implementado de forma iterativa, com uma janela [low, high] que encolhe, em vez de recursiva, de modo que um array muito grande nunca corre o risco de um frame de pilha por bisseção.

Exemplo clássico

classic/BinarySearch é genérico sobre Comparator<? super T> — sem o atalho de Arrays.binarySearch. O laço reduz uma janela [low, high] a cada iteração em vez de usar recursão, o que é o que mantém isso seguro em arrays grandes demais para uma pilha de chamadas recursiva lidar confortavelmente. BinarySearchTest cobre um alvo no meio, no início, no final, um alvo ausente, um array vazio, um array de um único elemento, cada posição de um array de tamanho par (exercitando as duas direções de arredondamento do ponto médio), e ambas as proteções contra argumento nulo.

Exemplo aplicado: consulta de snapshot de chaves PIX do BACEN

applied/RegisteredPixKeyLookup verifica se uma chave PIX está registrada em um snapshot noturno, já ordenado, de todas as chaves registradas — o tipo de exportação em lote que um job de reconciliação extrai uma vez e depois consulta muitas vezes. Diferentemente de uma trie construída incrementalmente à medida que as chaves são registradas em tempo real, isto presume que todo o conjunto de chaves já é conhecido e está fixo para o dia: ordená-lo uma vez, de antemão, e fazer busca binária a cada consulta é mais barato do que manter uma estrutura viva para dados que não mudam até o snapshot do dia seguinte. RegisteredPixKeyLookupTest cobre uma chave registrada, uma chave não registrada, e ambas as proteções contra argumento nulo.

Benchmark

./gradlew :searching:binary-search:jmh

Execução real nesta máquina (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 de medição, 1 fork). Mesmo pior caso, mesmos tamanhos, mesma máquina do benchmark de Linear Search deste repositório:

Essa é a alegação de O(log n), tornada inconfundível: um aumento de 100x no tamanho (100→10,000) custa apenas ~2.15x mais tempo; um novo aumento de 100x (10,000→1,000,000) custa apenas ~1.47x mais — multiplicadores decrescentes para o mesmo crescimento proporcional nos dados, exatamente a assinatura de uma escala logarítmica (log₂(10,000)/log₂(100) ≈ 2.0, log₂(1,000,000)/log₂(10,000) ≈ 1.5 — a forma prevista, batendo quase exatamente). Contra os 1,676,427.30 ns do Linear Search para a mesma pergunta em size=1,000,000, este módulo responde em 30.29 ns — ~55,353x mais rápido, na mesma máquina, para a mesma pergunta "está aí ou não". A única diferença é um bit de informação que o linear search não tem como usar: os dados estão ordenados.

Quando não usar

• Os dados não estão ordenados, e não serão consultados um número de vezes suficiente para justificar ordená-los uma vez? O Linear Search deste repositório evita completamente o custo de ordenação — vale a pena só se o número de consultas permanecer pequeno.
• Os dados mudam com frequência (inserções/remoções frequentes) e precisam continuar pesquisáveis a cada passo? Manter um array ordenado sob esse tipo de alteração custa O(n) por inserção para manter — uma estrutura de árvore autobalanceada (uma árvore AVL ou uma B-tree, por exemplo) mantém as duas operações rápidas em vez de trocar uma pela outra.
• Precisa da chave mais próxima, não apenas de uma correspondência exata, ou de um intervalo ordenado? Esta implementação retorna -1 quando não encontra e descarta exatamente onde o alvo teria ficado — uma variante ciente de floor/ceiling precisaria retornar esse limite em vez disso.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :searching:binary-search:jacocoTestReport

Relatório em searching/binary-search/build/reports/jacoco/test/html/index.html.

Leitura complementar

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3ª/4ª ed., o Problema 2-4 cobre recorrências relacionadas a busca; a própria busca binária é um exemplo recorrente ao longo dos capítulos de dividir para conquistar.
• Sedgewick & Wayne — Algorithms, 4ª ed., seção 3.1, "Symbol Tables" — apresenta a busca binária como BinarySearch.rank, a linha de base que toda tabela de símbolos ordenada do livro aprimora.

Testes unitários

package com.algorithms.searching.binarysearch.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class BinarySearchTest {

    @Test
    void findsATargetInTheMiddle() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 5, Comparator.naturalOrder());

        assertThat(index).isEqualTo(2);
    }

    @Test
    void findsATargetAtTheStart() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 1, Comparator.naturalOrder());

        assertThat(index).isZero();
    }

    @Test
    void findsATargetAtTheEnd() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 9, Comparator.naturalOrder());

        assertThat(index).isEqualTo(4);
    }

    @Test
    void returnsMinusOneWhenTheTargetIsMissing() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 4, Comparator.naturalOrder());

        assertThat(index).isEqualTo(-1);
    }

    @Test
    void returnsMinusOneOnAnEmptyArray() {
        Integer[] array = {};

        int index = BinarySearch.search(array, 1, Comparator.naturalOrder());

        assertThat(index).isEqualTo(-1);
    }

    @Test
    void singleElementArrayFindsItsOnlyElement() {
        Integer[] array = {42};

        int index = BinarySearch.search(array, 42, Comparator.naturalOrder());

        assertThat(index).isZero();
    }

    @Test
    void evenSizedArrayFindsEveryElement() {
        Integer[] array = {1, 2, 3, 4};

        for (int expected = 0; expected < array.length; expected++) {
            assertThat(BinarySearch.search(array, array[expected], Comparator.naturalOrder())).isEqualTo(expected);
        }
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> BinarySearch.search(null, 1, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> BinarySearch.search(new Integer[] {1}, 1, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.searching.binarysearch.applied;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class RegisteredPixKeyLookupTest {

    @Test
    void reportsTrueForARegisteredKey() {
        RegisteredPixKeyLookup lookup = new RegisteredPixKeyLookup(
                new String[] {"alice@bank.com", "bob@bank.com", "carol@bank.com"});

        assertThat(lookup.isRegistered("bob@bank.com")).isTrue();
    }

    @Test
    void reportsFalseForAnUnregisteredKey() {
        RegisteredPixKeyLookup lookup = new RegisteredPixKeyLookup(
                new String[] {"alice@bank.com", "bob@bank.com", "carol@bank.com"});

        assertThat(lookup.isRegistered("dave@bank.com")).isFalse();
    }

    @Test
    void rejectsANullSnapshot() {
        assertThatThrownBy(() -> new RegisteredPixKeyLookup(null)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullKey() {
        RegisteredPixKeyLookup lookup = new RegisteredPixKeyLookup(new String[] {"alice@bank.com"});

        assertThatThrownBy(() -> lookup.isRegistered(null)).isInstanceOf(IllegalArgumentException.class);
    }
}

Ver relatório completo de cobertura JaCoCo →