Algoritmos de Búsqueda

La búsqueda es el proceso de localizar un elemento dentro de una estructura de datos. La eficiencia de una búsqueda depende directamente de la organización de los datos y del algoritmo seleccionado. A continuación, se exploran dos enfoques fundamentales con implementaciones en Java.

1. Búsqueda Secuencial

Es el método más directo y no requiere que los datos estén ordenados. Consiste en comparar secuencialmente cada elemento de la colección con el valor objetivo hasta encontrarlo o llegar al final. Su complejidad temporal es O(n).

Este método es efectivo para listas pequeñas o no ordenadas, pero se vuelve ineficiente con grandes volúmenes de datos.

public class BusquedaLineal {
    public static void main(String[] args) {
        int[] datos = {45, 12, 67, 23, 89, 34, 56};
        int objetivo = 23;
        
        int resultado = buscarLinealmente(datos, objetivo);
        System.out.println(resultado != -1 ? "Encontrado en índice: " + resultado : "No encontrado");
    }

    public static int buscarLinealmente(int[] coleccion, int clave) {
        for (int i = 0; i < coleccion.length; i++) {
            if (coleccion[i] == clave) {
                return i;
            }
        }
        return -1;
    }
}

2. Búsqueda Binaria

Este algoritmo es significativamente más rápido para conjuntos de datos ordenados, con una complejidad O(log n). Funciona dividiendo repetidamente a la mitad el intervalo de búsqueda hasta localizar el valor o determinar su ausencia.

Una implementación iterativa clásica utiliza dos punteros, inicio y fin, para definir los límites del subarreglo activo.

public class BusquedaBinaria {
    public static void main(String[] args) {
        int[] arregloOrdenado = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int valor = 23;
        
        int posicion = busquedaBinariaRecursiva(arregloOrdenado, valor, 0, arregloOrdenado.length - 1);
        System.out.println("Posición del elemento: " + posicion);
    }

    // Implementación recursiva
    private static int busquedaBinariaRecursiva(int[] arr, int busqueda, int izquierda, int derecha) {
        if (izquierda > derecha) {
            return -1;
        }
        
        int puntoMedio = izquierda + (derecha - izquierda) / 2;
        
        if (arr[puntoMedio] == busqueda) {
            return puntoMedio;
        } else if (arr[puntoMedio] > busqueda) {
            return busquedaBinariaRecursiva(arr, busqueda, izquierda, puntoMedio - 1);
        } else {
            return busquedaBinariaRecursiva(arr, busqueda, puntoMedio + 1, derecha);
        }
    }
}

3. Otras Técnicas de Búsqueda Avanzada

Existen variaciones y extensiones que optimizan la búsqueda bajo condiciones específicas:

• Búsqueda por Interpolación: Mejora la búsqueda binaria cuando los datos están uniformemente distribuidos. Estima la posición del objetivo calculando una proporción basada en los valores de los extremos del intervalo actual.
• Búsqueda de Fibonacci: Utiliza la secuencia de Fibonacci para dividir el arreglo en partes que se aproximan a la proporción áurea (≈0.618). Puede ser ventajoso cuando el acceso a la memoria es más eficiente para ciertos índices.
• Búsqueda Indexada (o por bloques): Divide el conjunto de datos en bloques y mantiene un índice con el valor máximo de cada bloque. Primero se busca en el índice para localizar el bloque, y luego se realiza una búsqueda secuencial dentro de ese bloque.
• Búsqueda en Árboles (BST): Los árboles binarios de búsqueda permiten una búsqueda eficiente O(log n) manteniendo la propiedad de que todos los nodos en el subárbol izquierdo son menores y los del derecho son mayores.

Algoritmos de Ordenación

La ordenación es fundamental para organizar datos y mejorar la eficiencia de operaciones posetriores, como las búsquedas. A continuación, se presentan dos algoritmos comunes.

1. Ordenación Burbuja

Es un algoritmo sencillo que ordena la lista repetidamente intercambiando elementos adyacentes si están en el orden incorrecto. El elemento mayor "flota" gradualmente hacia el final en cada pasada. Su complejidad promedio es O(n²).

public class OrdenBurbuja {
    public static void main(String[] args) {
        int[] numeros = {64, 34, 25, 12, 22, 11, 90};
        
        ordenamientoBurbuja(numeros);
        System.out.println("Arreglo ordenado:");
        for (int num : numeros) {
            System.out.print(num + " ");
        }
    }

    public static void ordenamientoBurbuja(int[] arr) {
        int longitud = arr.length;
        boolean intercambio;
        
        for (int i = 0; i < longitud - 1; i++) {
            intercambio = false;
            for (int j = 0; j < longitud - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Intercambio de elementos
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    intercambio = true;
                }
            }
            // Si no hubo intercambios, el arreglo ya está ordenado
            if (!intercambio) break;
        }
    }
}

2. Ordenación por Inserción

Construye el arreglo ordenado final un elemento a la vez. Cada nuevo elemento se inserta en su posición correcta dentro de la porción ya ordenada del arreglo. Es eficiente para listas pequeñas o casi ordenadas, con una complejidad O(n²) en el peor caso, pero O(n) en el mejor.

public class OrdenInsercion {
    public static void main(String[] args) {
        int[] datos = {12, 11, 13, 5, 6};
        
        ordenamientoPorInsercion(datos);
        System.out.println("Arreglo ordenado:");
        for (int dato : datos) {
            System.out.print(dato + " ");
        }
    }

    public static void ordenamientoPorInsercion(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int clave = arr[i];
            int j = i - 1;
            
            // Desplaza los elementos mayores que la clave hacia la derecha
            while (j >= 0 && arr[j] > clave) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = clave;
        }
    }
}

3. Otros Algoritmos de Ordenación Notables

• Ordenación por Selección: En cada iteración, encuentra el elemento mínimo del subarreglo no ordenado y lo coloca al inicio. También tiene una complejidad O(n²).
• Ordenación Rápida (Quick Sort): Utiliza la estrategia de divide y vencerás. Selecciona un elemento como pivote, particiona el arreglo alrededor de él y ordena recursivamente las sub-particiones. Su promedio es O(n log n), pero puede degradarse a O(n²) con una mala selección del pivote.
• Ordenación por Mezcla (Merge Sort): Otro algoritmo divide y vencerás O(n log n) y estable que divide el arreglo en mitades, las ordena recursivamente y luego fusiona los resultados. Su principal ventaja es su complejidad garantizada, aunque requiere espacio adicional O(n).