Pausa para el café #156. Cómo utilizar el método Arrays.binarySearch() en Java

Fuente: FreeCodeCamp Con este artículo, aprenderá cómo utilizar el método Arrays.binarySearch() en Java.

¿Qué es Arrays.binarySearch() en Java?

La documentación oficial para el método Arrays.binarySearch() establece:

• Este método busca el valor especificado en la matriz de bytes especificada utilizando un algoritmo de búsqueda binaria.
• La matriz debe ordenarse (usando el método sort(byte[]) ) antes de realizar la llamada. Si no se ordena, no se determinarán los resultados.
• Si la matriz contiene varios elementos con el valor especificado, no hay garantía de cuál se encontrará.

En términos simples, el método Arrays.binarySearch() puede buscar un elemento determinado en una matriz ordenada y devolver su índice si lo encuentra.

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);

	}
}

El método Arrays.binarySearch() toma la matriz que desea buscar como primer argumento y la clave que está buscando como segundo argumento. El resultado del programa anterior será: Recuerde que el método devuelve el índice del elemento encontrado, no el elemento en sí. De esta manera puedes almacenar el índice como un número entero como el usado en este ejemplo. De forma predeterminada, el método utiliza el primer índice de la matriz como punto inicial de la búsqueda y la longitud de la matriz como punto final de la búsqueda. En este caso, el índice inicial es 0 y el índice final es 6. En lugar de utilizar el índice inicial y final predeterminado, puede definirlos usted mismo. Por ejemplo, si desea buscar desde el índice 2 al índice 4, puede hacerlo así:

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);

	}
}

En este caso, el método Arrays.binarySearch() toma la matriz que desea buscar como primer argumento, el índice inicial como segundo argumento, el índice final como tercero y la clave como cuarto. Siempre que mantenga el índice final dentro de la longitud de la matriz, el método debería funcionar bien. Pero si lo excede, obtendrá una excepción de índice de matriz fuera de rango . Es bastante simple, ¿verdad? El método devuelve el índice del elemento si se encuentra. Pero ¿qué pasa si no encuentra el elemento dado?

¿Qué sucede cuando Arrays.binarySearch() no encuentra un elemento determinado?

Echemos otro vistazo a la documentación oficial del método Arrays.binarySearch() :

• El método encuentra el índice de una clave en los resultados de la búsqueda si está contenida en la matriz dentro del rango especificado; de lo contrario obtenemos (-(punto de inserción) - 1) .
• El punto de inserción se define como el punto en el que se insertará una clave en la matriz: el índice del primer elemento del rango es mayor que la clave, o toIndex (índice final) si todos los elementos del rango son menores que el clave especificada.
• Tenga en cuenta que el valor de retorno solo será mayor o igual a 0 cuando se encuentre la clave.

No muy claro ¿verdad? La primera línea indica que el método devolverá el índice de la clave de la búsqueda si se encuentra en la matriz. Si no se encuentra, la salida será igual al valor (-(punto de inserción) - 1) . Dependiendo de la clave de búsqueda, el punto de inserción puede tener diferentes significados. Digamos que tenemos una matriz [5, 6, 7, 8, 9, 10] y una clave de búsqueda de 0 , que claramente no está en la matriz. En este caso, la clave de búsqueda es menor que todos los elementos de la matriz. Pero el primer elemento que es mayor que la clave de búsqueda es 5 . Así, en nuestro caso el punto de inserción será: Puedes implementar esto en un fragmento 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
	}
}

Supongamos nuevamente que tenemos una matriz [5, 6, 7, 8, 9, 10] y una clave de búsqueda de 12 , que claramente no está en la matriz. En este caso, la clave de búsqueda es mayor que todos los elementos de la matriz. Aquí el punto de inserción será así: Recuerde que si no especifica manualmente el índice final, el método utiliza la longitud de la matriz como índice final, que en este caso es 6 . Puedes implementar esto en un fragmento 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
	}
}

Sin embargo, los resultados cambiarán si define los índices inicial y final manualmente:

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

	}
}

Intente calcular los valores usted mismo. También puedes usar el método Arrays.binarySearch() con 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));

	}
}

Se aplican los mismos principios si no se encuentra la clave de búsqueda especificada. Pero al comparar entre un carácter de la matriz y una clave de búsqueda determinada, se utilizará el código ASCII del carácter correspondiente. Es decir, A (65) será menor que a (97) . Tenga esto en cuenta al verificar la salida de su programa.