La eficiencia en la recuperación de datos es crucial en cualquier sistema informático. Este artículo explora varios algoritmos de búsqueda comunes, desde los más sencillos hasta los más optimizados, detallando su funcionamiento y proporcionando ejemplos de implementación en Java.

Búsqueda Lineal (Secuencial)

La búsqueda lineal, también conocida como búsqueda secuencial, representa el método más básico para encontrar un elemento dentro de una colección de datos. Su procedimiento es directo: examina cada elemento de la colección de manera consecutiva, desde el inicio hasta el final, hasta que localiza el valor deseado o concluye la revisión de toda la estructura de datos. Es aplicable en arreglos no ordenados y su complejidad temporal es O(n).

public int buscarSecuencialmente(int[] arregloNumeros, int valorObjetivo) {
    for (int indice = 0; indice < arregloNumeros.length; indice++) {
        if (arregloNumeros[indice] == valorObjetivo) {
            return indice; // Retorna el índice si el valor es encontrado
        }
    }
    return -1; // Retorna -1 si el valor no está presente en el arreglo
}

Búsqueda Binaria

La búsqueda binaria es un algoritmo considerablemente más eficiente que su contraparte lineal, pero impone una condición fundamental: el arreglo o la lista de datos debe estar estrictamente ordenado. Si los datos no cumplen con este requisito, es indispensable realizar una fase de ordenamiento previo. Su notable eficiencia radica en su estartegia de "divide y vencerás", reduciendo el espacio de búsqueda a la mitad en cada iteración.

Implementación Estándar

El algoritmo opera comparando el valor objetivo con el elemento ubicado en la posición central del segmento actual del arreglo. Si hay una coincidencia, el elemento ha sido encontrado. Si el valor buscado es menor que el elemento central, la búsqueda se restringe a la mitad inferior del segmento. Por el contrario, si es mayor, la búsqueda se limita a la mitad superior. Este proceso se replica de forma recursiva (o iterativa) hasta que el elemento es hallado o el rango de búsqueda se agota.

public int buscarBinario(int[] datosOrdenados, int limiteInferior, int limiteSuperior, int valorBuscado) {
    // Caso base: el segmento de búsqueda está vacío o los límites son inválidos
    if (limiteInferior > limiteSuperior) {
        return -1;
    }

    // Calcular el índice central para evitar desbordamiento en enteros
    int indiceMedio = limiteInferior + (limiteSuperior - limiteInferior) / 2;

    if (datosOrdenados[indiceMedio] == valorBuscado) {
        return indiceMedio; // Elemento encontrado
    } else if (datosOrdenados[indiceMedio] > valorBuscado) {
        // El valor buscado se encuentra en la mitad izquierda
        return buscarBinario(datosOrdenados, limiteInferior, indiceMedio - 1, valorBuscado);
    } else {
        // El valor buscado se encuentra en la mitad derecha
        return buscarBinario(datosOrdenados, indiceMedio + 1, limiteSuperior, valorBuscado);
    }
}

Búsqueda de Todas las Ocurrencias

Cuando se requiere encontrar todas las ocurrencias de un valor específico dentro de un arreglo ordenado, se puede emplear una adaptación de la búsqueda binaria. Primero, se localiza una de las instancias del valor objetivo (generalmente la primera que se encuentra con el algoritmo estándar). Una vez identificada, se realizan expansiones hacia la izquierda y hacia la derecha de ese punto, recolectando todos los índices donde el valor coincide. Es esencial manejar los límites del arreglo para prevenir accesos fuera de rango.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public List<Integer> buscarTodasOcurrenciasBinario(int[] arreglo, int valorATarget) {
    List<Integer> indicesEncontrados = new ArrayList<>();
    if (arreglo == null || arreglo.length == 0) {
        return indicesEncontrados;
    }

    int izq = 0;
    int der = arreglo.length - 1;
    int indiceHallado = -1;

    // Paso 1: Encontrar una ocurrencia del valor objetivo
    while (izq <= der) {
        int centro = izq + (der - izq) / 2;
        if (arreglo[centro] == valorATarget) {
            indiceHallado = centro;
            break; // Una ocurrencia ha sido encontrada
        } else if (arreglo[centro] < valorATarget) {
            izq = centro + 1;
        } else {
            der = centro - 1;
        }
    }

    if (indiceHallado != -1) {
        // Paso 2: Buscar ocurrencias hacia la izquierda del indiceHallado
        int tempIzquierdo = indiceHallado - 1;
        while (tempIzquierdo >= 0 && arreglo[tempIzquierdo] == valorATarget) {
            indicesEncontrados.add(tempIzquierdo);
            tempIzquierdo--;
        }

        // Paso 3: Añadir la ocurrencia inicialmente hallada
        indicesEncontrados.add(indiceHallado);

        // Paso 4: Buscar ocurrencias hacia la derecha del indiceHallado
        int tempDerecho = indiceHallado + 1;
        while (tempDerecho < arreglo.length && arreglo[tempDerecho] == valorATarget) {
            indicesEncontrados.add(tempDerecho);
            tempDerecho++;
        }
    }
    
    // Opcional: ordenar los índices para que estén en orden ascendente
    Collections.sort(indicesEncontrados);
    return indicesEncontrados;
}

Búsqueda por Interpolación

La búsqueda por interpolación se presenta como una optimización de la búsqueda binaria, destacando su eficacia cuando los elementos de un arreglo están distribuidos de manera uniforme. A diferencia de la búsqueda binaria, que divide el arreglo por la mitad de forma constante, la búsqueda por interpolación estima una posición más probable para el objetivo. Esta estimación se basa en el valor del objetivo y en los valores presentes en los extremos del segmento de búsqueda actual, permitiendo saltos más grandes o más pequeños según la cercanía del objetivo. Sin embargo, si la distribución de los datos es muy irregular, su rendimiento podría ser inferior al de la búsqueda binaria.

public int busquedaPorInterpolacion(int[] conjuntoValores, int indiceInicio, int indiceFin, int valorBuscado) {
    // Validar los límites del rango y si el valorBuscado está dentro de los extremos
    if (indiceInicio > indiceFin || valorBuscado < conjuntoValores[indiceInicio] || valorBuscado > conjuntoValores[indiceFin]) {
        return -1;
    }

    // Calcular la posición estimada de manera adaptativa
    int posicionEstimada;
    if (conjuntoValores[indiceFin] == conjuntoValores[indiceInicio]) { // Prevenir división por cero
        posicionEstimada = indiceInicio; // Si todos los elementos son iguales, el objetivo solo puede estar en el inicio
    } else {
        posicionEstimada = indiceInicio + ((indiceFin - indiceInicio) * (valorBuscado - conjuntoValores[indiceInicio])) / (conjuntoValores[indiceFin] - conjuntoValores[indiceInicio]);
    }
    
    // Asegurarse de que la posición estimada esté dentro del rango válido
    if (posicionEstimada < indiceInicio || posicionEstimada > indiceFin) {
        return -1; // Estimación fuera de rango
    }

    if (conjuntoValores[posicionEstimada] == valorBuscado) {
        return posicionEstimada;
    } else if (conjuntoValores[posicionEstimada] < valorBuscado) {
        return busquedaPorInterpolacion(conjuntoValores, posicionEstimada + 1, indiceFin, valorBuscado);
    } else {
        return busquedaPorInterpolacion(conjuntoValores, indiceInicio, posicionEstimada - 1, valorBuscado);
    }
}

Búsqueda de Fibonacci

La búsqueda de Fibonacci, también conocida como búsqueda por división áurea, es otro algoritmo aplicable a arreglos ordenados. Su denominación proviene de la utilización de números de Fibonacci para determinar los puntos de división del arreglo, buscando emular la proporción áurea. Este método resulta especialmente útil en escenarios donde el costo de acceso a los elementos del arreglo varía, o cuando la búsqueda por interpolación podría ser ineficiente debido a la distribución particular de los datos.

Los pasos fundamentales de la búsqueda de Fibonacci son:

• Generación de la Secuencia de Fibonacci: Se construye una secuencia de números de Fibonacci hasta alcanzar un tamaño que sea al menos igual a la longitud del arreglo donde se realizará la búsqueda.
• Ajuste del Tamaño del Arreglo: El arreglo original se "extiedne" conceptualmente (o físicamente, copiando el último elemento) para que su longitud coincida con un número de Fibonacci (Fk). Esta extensión garantiza que las divisiones basadas en los números de Fibonacci sean válidas.
• Inicialización: Se configuran los punteros de inicio (bajo) y fin (alto) que delimitarán el rango de búsqueda.
• Proceso Iterativo: En cada iteración, se calcula un punto medio (indiceMedio) utilizando la fórmula: indiceMedio = bajo + SerieFib[k-1] - 1. Se compara el elemento en indiceMedio con el objetivo:
  • Si el elemento es menor que el objetivo, la búsqueda prosigue en la sección derecha del arreglo, ajustando bajo y el índice k (k = k - 2).
  • Si el elemento es mayor que el objetivo, la búsqueda se centra en la sección izquierda, ajustando alto y k (k = k - 1).
  • Si los elementos son iguales, se ha localizado el objetivo. Es crucial verificar que el indiceMedio resultante se encuentre dentro de los límites del arreglo original, ya que el arreglo pudo haber sido extendido.

// Método auxiliar para generar una secuencia de Fibonacci con F0=1, F1=1
private void construirSerieFibonacci(int maxIndice, int[] serieFib) {
    if (maxIndice >= 0) {
        serieFib[0] = 1;
    }
    if (maxIndice >= 1) {
        serieFib[1] = 1;
    }
    for (int i = 2; i <= maxIndice; i++) {
        serieFib[i] = serieFib[i - 1] + serieFib[i - 2];
    }
}

public int buscarFibonacci(int[] conjuntoDatos, int valorBuscado) {
    if (conjuntoDatos == null || conjuntoDatos.length == 0) {
        return -1;
    }
    if (conjuntoDatos.length == 1) {
        return conjuntoDatos[0] == valorBuscado ? 0 : -1;
    }

    int limiteInferior = 0;
    int limiteSuperior = conjuntoDatos.length - 1;

    // Generar una secuencia de Fibonacci. Un tamaño de 20 es generalmente suficiente.
    int[] serieFibonacci = new int[20];
    construirSerieFibonacci(19, serieFibonacci); // Popula serieFibonacci[0] a serieFibonacci[19]

    int indiceK = 0; // Índice en la secuencia de Fibonacci
    // Encontrar el número de Fibonacci más pequeño que sea mayor o igual a la longitud del arreglo
    while (serieFibonacci[indiceK] < conjuntoDatos.length) {
        indiceK++;
    }

    // Extender el arreglo original a la longitud de serieFibonacci[indiceK]
    // Los espacios adicionales se rellenan con el último valor del arreglo original
    int[] arregloExtend = new int[serieFibonacci[indiceK]];
    System.arraycopy(conjuntoDatos, 0, arregloExtend, 0, conjuntoDatos.length);
    for (int i = conjuntoDatos.length; i < serieFibonacci[indiceK]; i++) {
        arregloExtend[i] = conjuntoDatos[conjuntoDatos.length - 1];
    }

    while (limiteInferior <= limiteSuperior) {
        // Calcular el índice medio usando la secuencia de Fibonacci
        // Es limiteInferior + (F[k-1] - 1)
        int indiceMedio = limiteInferior + serieFibonacci[indiceK - 1] - 1;

        // Ajuste para asegurar que indiceMedio no exceda los límites del arreglo extendido
        if (indiceMedio >= arregloExtend.length) {
            indiceMedio = arregloExtend.length - 1; 
        }

        if (arregloExtend[indiceMedio] < valorBuscado) {
            // El valor objetivo está en la sección derecha (tamaño F[k-2])
            limiteInferior = indiceMedio + 1;
            indiceK -= 2; // Ajustar k para la sub-sección derecha
        } else if (arregloExtend[indiceMedio] > valorBuscado) {
            // El valor objetivo está en la sección izquierda (tamaño F[k-1])
            limiteSuperior = indiceMedio - 1;
            indiceK -= 1; // Ajustar k para la sub-sección izquierda
        } else {
            // Elemento encontrado. Verificar si el índice está en el arreglo original.
            if (indiceMedio < conjuntoDatos.length) {
                return indiceMedio;
            } else {
                // Si el índice está en la parte extendida, significa que el valor buscado
                // es el mismo que el último elemento del arreglo original.
                return conjuntoDatos.length - 1;
            }
        }
    }
    return -1; // El valor objetivo no fue encontrado
}