Pausa para café #156. Como usar o método Arrays.binarySearch() em Java

Fonte: FreeCodeCamp Com este artigo, você aprenderá como usar o método Arrays.binarySearch() em Java.

O que é Arrays.binarySearch() em Java?

A documentação oficial do método Arrays.binarySearch() afirma:

• Este método pesquisa na matriz de bytes especificada o valor especificado usando um algoritmo de pesquisa binária.
• A matriz deve ser classificada (usando o método sort(byte[]) ) antes da chamada ser feita. Se não for classificado, os resultados não serão determinados.
• Se a matriz contiver vários elementos com o valor especificado, não há garantia de qual deles será encontrado.

Em termos simples, o método Arrays.binarySearch() pode procurar um determinado elemento em um array classificado e retornar seu índice se encontrado.

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';

		int foundItemIndex = Arrays.binarySearch(vowels, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

O método Arrays.binarySearch() usa o array que você deseja pesquisar como o primeiro argumento e a chave que você está procurando como o segundo argumento. A saída do programa acima será: Lembre-se que o método retorna o índice do elemento encontrado, e não o elemento em si. Desta forma você pode armazenar o índice como um número inteiro como o usado neste exemplo. Por padrão, o método usa o primeiro índice do array como ponto inicial da pesquisa e o comprimento do array como ponto final da pesquisa. Nesse caso, o índice inicial é 0 e o índice final é 6. Em vez de usar o índice inicial e final padrão, você mesmo pode defini-los. Por exemplo, se você quiser pesquisar do índice 2 ao índice 4, você poderia fazer assim:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

Nesse caso, o método Arrays.binarySearch() considera o array que você deseja pesquisar como o primeiro argumento, o índice inicial como o segundo argumento, o índice final como o terceiro e a chave como o quarto. Contanto que você mantenha o índice final dentro do comprimento da matriz, o método deverá funcionar bem. Mas se você exceder, você obterá uma exceção Array index out of range . É bem simples, certo? O método retorna o índice do elemento se for encontrado. Mas o que acontece se não encontrar o elemento fornecido?

O que acontece quando Arrays.binarySearch() não encontra um determinado elemento?

Vamos dar uma olhada na documentação oficial do método Arrays.binarySearch() :

• O método encontra o índice de uma chave nos resultados da pesquisa se ela estiver contida na matriz dentro do intervalo especificado; caso contrário, obteremos (-(ponto de inserção) - 1) .
• O ponto de inserção é definido como o ponto em que uma chave será inserida no array: o índice do primeiro elemento do intervalo é maior que a chave, ou toIndex (índice final) se todos os elementos do intervalo forem menores que o chave especificada.
• Observe que o valor de retorno só será maior ou igual a 0 quando a chave for encontrada.

Não é muito claro, certo? A primeira linha afirma que o método retornará o índice da chave da pesquisa se for encontrada no array. Se não for encontrado, a saída será igual ao valor (-(ponto de inserção) - 1) . Dependendo da chave de pesquisa, o ponto de inserção pode ter significados diferentes. Digamos que temos um array [5, 6, 7, 8, 9, 10] e uma chave de pesquisa 0 , que claramente não está no array. Neste caso, a chave de pesquisa é menor que todos os elementos do array. Mas o primeiro elemento maior que a chave de pesquisa é 5 . Assim, no nosso caso o ponto de inserção será: Você pode implementar isso em um trecho de código como este:

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 0)); // -1
	}
}

Vamos supor novamente que temos um array [5, 6, 7, 8, 9, 10] e uma chave de pesquisa de 12 , que claramente não está no array. Neste caso, a chave de pesquisa é maior que todos os elementos do array. Aqui o ponto de inserção será assim: Lembre-se de que se você não especificar manualmente o índice final, o método usará o comprimento do array como índice final, que neste caso é 6 . Você pode implementar isso em um trecho de código como este:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 12)); // -7
	}
}

No entanto, os resultados serão alterados se você definir manualmente os índices inicial e final:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		int startIndex = 1;
		int endIndex = 3;

		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2
		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4

	}
}

Tente calcular você mesmo os valores. Você também pode usar o método Arrays.binarySearch() com símbolos como este:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key));

	}
}

Os mesmos princípios se aplicam se a chave de pesquisa especificada não for encontrada. Mas ao comparar entre um caractere na matriz e uma determinada chave de pesquisa, será usado o código ASCII do caractere correspondente. Ou seja, A (65) será menor que a (97) . Leve isso em consideração ao fazer uma verificação cruzada da saída do seu programa.