Búsqueda

La búsqueda (Search) se refiere al proceso de localizar si existe un elemento específico y su posición concreta en un conjunto de datos. Es una operación básica en la que casi todos los programas están involucrados.


Comparación de tres algoritmos de búsqueda

Comparación de complejidad de algoritmos de búsqueda — número de operaciones cuando n=1000
Resumen de comparación de tres algoritmos de búsqueda

Búsqueda lineal O(n)

No requiere orden

Comparar uno a uno, simple y confiable

Adecuado para: datos pequeños o desordenados

Búsqueda binaria O(log n)

Requiere orden

Cada vez se divide a la mitad y se descarta la otra mitad

Adecuado para: solución general para datos ordenados

Búsqueda por interpolación O(log log n)

Requiere orden + distribución uniforme

Estima la posición según la proporción del valor

Adecuado para: óptimo cuando la distribución es uniforme

Búsqueda lineal

Compara uno a uno desde el primer elemento hasta encontrar el objetivo o recorrer todo el conjunto. No requiere datos ordenados. Complejidad temporal O(n).

Búsqueda binaria

Requiere que los datos estén ordenados. Cada vez compara con el elemento central y reduce el rango de búsqueda a la mitad. Complejidad temporal O(log n).

Búsqueda por interpolación

Optimización de la búsqueda binaria. No toma el punto medio, sino que estima la posición probable según el valor objetivo. Cuando los datos tienen una distribución uniforme, puede alcanzar O(log log n).

Ejemplo

#include <stdio.h>

/* Búsqueda lineal: O(n), no requiere orden */
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

/* Búsqueda binaria: O(log n), requiere que el arreglo esté ordenado (ascendente) */
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;  /* Escritura para evitar desbordamiento */
        if (arr[mid] == target) return mid;    /* Encontrado */
        if (arr[mid] < target)
            left = mid + 1;   /* El objetivo está en la mitad derecha */
        else
            right = mid - 1;  /* El objetivo está en la mitad izquierda */
    }
    return -1;  /* No encontrado */
}

/* Búsqueda por interpolación: O(log log n) promedio, requiere distribución uniforme */
int interpolationSearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        /* Fórmula de interpolación: estima la posición según la proporción del valor */
        int pos = low + ((target - arr[low]) * (high - low))
                        / (arr[high] - arr[low]);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target)
            low = pos + 1;
        else
            high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int n = 9;

    printf("Búsqueda lineal 50: índice %d\n", linearSearch(arr, n, 50));      /* Salida: 4 */
    printf("Búsqueda binaria 50: índice %d\n", binarySearch(arr, 0, n-1, 50)); /* Salida: 4 */
    printf("Búsqueda por interpolación 50: índice %d\n", interpolationSearch(arr, n, 50)); /* Salida: 4 */
    return 0;
}

Resumen de comparación de complejidad

AlgoritmoComplejidad temporalRequiere ordenEscenario de aplicación
Búsqueda linealO(n)noDatos pequeños o desordenados
Búsqueda binariaO(log n)SíArreglo ordenado, general y eficiente
Búsqueda por interpolaciónO(log log n)PromedioSíEscenarios específicos con distribución uniforme de datos
Otras extensiones