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

Búsqueda binaria en PHP

JavaScript: implementación del algoritmo de búsqueda binaria

Python y listas: búsqueda binaria

Más tutoriales de Java

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
    *
    * @see https://parzibyte.me/blog/2018/10/31/comparar-cadenas-java-equals-compareto-forma-correcta/ 
    * @author parzibyte
    * @web 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
    *
    * @see https://parzibyte.me/blog/2018/10/31/comparar-cadenas-java-equals-compareto-forma-correcta/ 
    * @author parzibyte
    * @web 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.