Introducción
Acabamos de hacer el algoritmo de búsqueda binaria recursiva y secuencial en Java pero sobre arreglos numéricos. Ahora veamos cómo hacer exactamente lo mismo pero en un arreglo de cadenas.
Aquí cambia un poco la cosa, pues no podemos tratar a las cadenas como números, y las mismas tampoco son comparadas con los operadores de menor, mayor, igual, menor o igual o mayor o igual.
Lo que usaremos será el método compareTo, cuya referencia encuentras más abajo.
Ya no explicaré a detalle cómo es, visita el post que cito al inicio para que obtengas una idea más clara. Aquí sólo veremos el código de las funciones y la forma de llamarlas.
Lecturas recomendadas
Mira cómo funciona compareTo para comparar cadenas
JavaScript: implementación del algoritmo de búsqueda binaria
Python y listas: búsqueda binaria
Explicación del algoritmo
Veamos una pequeñísima explicación…
Lo que hacemos es tomar el valor de retorno de compareTo.
Si es 0, las cadenas son iguales.
Si es un número negativo entonces la primer cadena es menor que la segunda; en este caso comparamos a busqueda con elementoDelMedio, si el resultado es negativo significa que busqueda es menor, y partimos desde el centro - 1 hacia la izquierda.
Si no, desde el centro + 1 hasta la derecha.
Cuando izquierda es mayor que derecha se termina la recursión y se indica que el elemento no fue encontrado.
Búsqueda binaria recursiva en arreglo de cadenas
Aquí dejo la función.
/**
* Algoritmo de búsqueda binaria recursiva en Java.
* Esta vez para buscar en arreglos de Strings o cadenas
*
* https://parzibyte.me/blog/
* https://parzibyte.me/blog/posts/comparar-cadenas-java-equals-compareto-forma-correcta/
* @author parzibyte
* @web https://parzibyte.me/blog/
*/
public static int busquedaBinariaRecursiva(String[] arreglo, String busqueda, int izquierda, int derecha) {
// Si izquierda es mayor que derecha significa que no encontramos nada
if (izquierda > derecha) {
return -1;
}
// Calculamos las mitades...
int indiceDelElementoDelMedio = (int) Math.floor((izquierda + derecha) / 2);
String elementoDelMedio = arreglo[indiceDelElementoDelMedio];
// Primero vamos a comparar y luego vamos a ver si el resultado es negativo,
// positivo o 0
int resultadoDeLaComparacion = busqueda.compareTo(elementoDelMedio);
// Si el resultado de la comparación es 0, significa que ambos elementos son iguales
// y por lo tanto quiere decir que hemos encontrado la búsqueda
if (resultadoDeLaComparacion == 0) {
return indiceDelElementoDelMedio;
}
// Si no, entonces vemos si está a la izquierda o derecha
if (resultadoDeLaComparacion < 0) {
derecha = indiceDelElementoDelMedio - 1;
return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
} else {
izquierda = indiceDelElementoDelMedio + 1;
return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
}
}
La forma de llamarla la veremos al final.
Búsqueda binara secuencial en arreglo de cadenas
Lo mismo de arriba, pero con while. El código queda así:
/**
* Algoritmo de búsqueda binaria secuencial en Java.
* Esta vez para buscar en arreglos de Strings o cadenas
*
* https://parzibyte.me/blog/
* https://parzibyte.me/blog/posts/comparar-cadenas-java-equals-compareto-forma-correcta/
* @author parzibyte
* @web https://parzibyte.me/blog/
*/
public static int busquedaBinariaConWhile(String[] arreglo, String busqueda) {
int izquierda = 0, derecha = arreglo.length - 1;
while (izquierda <= derecha) {
// Calculamos las mitades...
int indiceDelElementoDelMedio = (int) Math.floor((izquierda + derecha) / 2);
String elementoDelMedio = arreglo[indiceDelElementoDelMedio];
// Primero vamos a comparar y ver si el resultado es negativo, positivo o 0
int resultadoDeLaComparacion = busqueda.compareTo(elementoDelMedio);
// Si el resultado de la comparación es 0, significa que ambos elementos son iguales
// y por lo tanto quiere decir que hemos encontrado la búsqueda
if (resultadoDeLaComparacion == 0) {
return indiceDelElementoDelMedio;
}
// Si no, entonces vemos si está a la izquierda o derecha
if (resultadoDeLaComparacion < 0) {
derecha = indiceDelElementoDelMedio - 1;
} else {
izquierda = indiceDelElementoDelMedio + 1;
}
}
// Si no se rompió el ciclo ni se regresó el índice, entonces el elemento no
// existe
return -1;
}
Igualmente el ejemplo de llamada queda al final.
Implementar funciones
Aquí una pequeña prueba. Definimos un arreglo y buscamos:
// Arreglo para probar
String[] arreglo = { "Chris", "Claire", "Django", "John", "Leon", "Morty", "Rick", "Saul", "Tuco", "Walter" };
String busqueda = "Morty";
// Probar primero con la recursiva
int indiceDelElementoBuscado = busquedaBinariaRecursiva(arreglo, busqueda, 0, arreglo.length - 1);
System.out.println("[Recursivo] -- El elemento buscado ("
+ busqueda
+ ") se encuentra en el index "
+ indiceDelElementoBuscado);
// Ahora con la que usa el ciclo while
indiceDelElementoBuscado = busquedaBinariaConWhile(arreglo, busqueda);
System.out.println("[Con ciclo While] -- El elemento buscado ("
+ busqueda
+ ") se encuentra en el index "
+ indiceDelElementoBuscado);
La salida es:
[Recursivo] – El elemento buscado (Morty) se encuentra en el index 5 [Con ciclo While] – El elemento buscado (Morty) se encuentra en el index 5
Con esto terminamos.