Fundamentos de la Búsqueda Binaria

La búsqueda binaria, frecuentemente denominada búsqueda de intervalo medio, es una técnica eficiente para localizar un elemento específico dentro de una colección de datos. Su principal ventaja radica en la reducción significativa del número de comparaciones necesarias, lo que se traduce en una velocidad de ejecución superior y un consumo mínimo de memoria del sistema. Sin embargo, para que este algoritmo funcione correctamente, es imperativo que la estructura de datos esté previamente ordenada. Esta dependencia del ordenamiento hace que las operaciones de inserción y eliminación sean más costosas en comparación con otras estructuras no ordenadas.

Implementación Iterativa

A continuación, se presenta una versión iterativa del algoritmo. Este enfoque es perferido en escenarios donde se desea evitar la sobrecarga asociada a las llamadas de funciones repetidas.

public class DemoBusquedaBinaria {
    public static void main(String[] args) {
        int[] conjuntoDatos = {3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101};
        System.out.println(ejecutarBusquedaIterativa(conjuntoDatos, 95));
    }

    /**
     * Realiza una búsqueda binaria utilizando un bucle.
     *
     * @param collection Arreglo ordenado de enteros
     * @param target     Valor que se desea encontrar
     * @return Índice del elemento o -1 si no existe
     */
    public static int ejecutarBusquedaIterativa(int[] collection, int target) {
        if (collection == null || collection.length == 0) {
            return -1;
        }

        int limiteInf = 0;
        int limiteSup = collection.length - 1;

        // Verificación rápida de límites
        if (target < collection[limiteInf] || target > collection[limiteSup]) {
            return -1;
        }

        while (limiteInf <= limiteSup) {
            int indiceMedio = limiteInf + (limiteSup - limiteInf) / 2;
            int valorMedio = collection[indiceMedio];

            if (valorMedio == target) {
                return indiceMedio;
            } else if (target < valorMedio) {
                limiteSup = indiceMedio - 1;
            } else {
                limiteInf = indiceMedio + 1;
            }
        }
        return -1;
    }
}

Cuando se utiliza la versión iterativa, el impacto se limita principalmente al uso de la CPU. En términos de modelo de memoria, la huella es negligible. La complejidad temporal es O(log n), mientras que la complejidad espacial se mantiene constante en O(1). Este algoritmo es fundamental y se utiliza extensivamente en estructuras como los árboles balanceados.

Implemnetación Recursiva

La recursividad implica que un método se invoque a sí mismo para resolver subproblemas más pequeños. Aunque el código suele ser más limpio, existen consideraciones de rendimiento.

public class DemoBusquedaBinaria {
    public static void main(String[] args) {
        int[] conjuntoDatos = {3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101};
        System.out.println(ejecutarBusquedaRecursiva(conjuntoDatos, 0, conjuntoDatos.length - 1, 28));
    }

    /**
     * Realiza una búsqueda binaria mediante recursividad.
     *
     * @param collection Arreglo ordenado
     * @param from       Índice inicial del rango
     * @param to         Índice final del rango
     * @param target     Elemento a buscar
     * @return Índice encontrado o -1
     */
    public static int ejecutarBusquedaRecursiva(int[] collection, int from, int to, int target) {
        if (from > to) {
            return -1;
        }

        int indiceMedio = from + (to - from) / 2;

        if (collection[indiceMedio] == target) {
            return indiceMedio;
        } else if (target > collection[indiceMedio]) {
            return ejecutarBusquedaRecursiva(collection, indiceMedio + 1, to, target);
        } else {
            return ejecutarBusquedaRecursiva(collection, from, indiceMedio - 1, target);
        }
    }
}

Es crucial entender que la recursión no solo consume ciclos de CPU. En la Máquina Virtual de Java (JVM), cada llamada recursiva ocupa espacio en la pila de hilos (thread stack). Si la profundidad de la recursión es excseiva, puede provocar un desbordamiento de pila. En tales casos, es necesario ajustar el tamaño de la pila mediante el parámetro -Xss durante la configuración del entorno de ejecución.