Procurando
O Java também fornece uma maneira conveniente de pesquisar, mas somente se o array já estiver classificado.
A Tabela 3.1 abrange as regras para pesquisa binária.
Vamos experimentar estas regras com um exemplo:
3: int[] numbers = {2,4,6,8};
4: System.out.println(Arrays.binarySearch(numbers, 2)); // 0
5: System.out.println(Arrays.binarySearch(numbers, 4)); // 1
6: System.out.println(Arrays.binarySearch(numbers, 1)); // -1
7: System.out.println(Arrays.binarySearch(numbers, 3)); // -2
8: System.out.println(Arrays.binarySearch(numbers, 9)); // -5
Tome nota do fato de que a linha 3 é uma matriz ordenada. Se não fosse, não poderíamos aplicar as outras regras. A linha 4 pesquisa o índice 2. A resposta é o índice 0. Linha 5 pesquisa o índice 4, que é 1.
A linha 5 pesquisa o índice 1. Embora 1 não esteja na lista, a pesquisa pode determinar que deve ser inserido no elemento 0 para preservar a ordem classificada. Desde 0 já significa algo para índices de array, o Java precisa subtrair 1 para nos dar a resposta de –1. Linha 7 é similar. Embora 3 não esteja na lista, precisaria ser inserido no elemento 1 para preservar a ordem classificada. Nós negamos e subtraímos 1 para consistência, obtendo –1 –1, também conhecido como –2. Finalmente, a linha 8 quer nos dizer que 9 deve ser inserido no índice 4. Novamente negamos e subtraia 1, obtendo –4 –1, também conhecido como –5.
O que você acha que acontece neste exemplo?
5: int numbers = new int[] {3,2,1};
6: System.out.println(Arrays.binarySearch(numbers, 2));
7: System.out.println(Arrays.binarySearch(numbers, 3));
Observe que na linha 5, a matriz não está classificada. Isso significa que a saída não será previsível.
Ao testar este exemplo, a linha 6 forneceu corretamente 1 como a saída. No entanto, a linha 3 deu a resposta errada. Os criadores do exame não esperam que você saiba quais valores incorretos saem. Assim que você vir a matriz não classificada, procure uma opção de resposta sobre imprevistos.
No exame, você precisa saber o que uma pesquisa binária retorna em vários cenários. Estranhamente, você não precisa saber porque “binário” está no nome. Caso você esteja curioso, uma busca binária divide o array em duas partes iguais (lembre-se de que 2 é binário) e determina qual metade do alvo é. Ele repete esse processo até restar apenas um elemento.