Este artículo explora diversas técnicas de búsqueda de datos, analizando su eficiencia y aplicabilidad en distintos escenarios.

1. Búsqueda Secuencial (Lineal)

Este método recorre los elementos uno por uno hasta encontrar el valor deseado. Es simple de implementar y no requiere que los datos estén ordenados, pero su rendimiento es lineal, O(n), lo que lo hace ineficiente para grandes conjuntos de datos.

int busquedaSecuencial(int datos[], int tamano, int clave) {
   for (int i = 0; i < tamano; i++) {
       if (datos[i] == clave) {
           return i; // Devuelve el índice si se encuentra
       }
   }
   return -1; // Devuelve -1 si no se encuentra
}

2. Búsqueda Binaria (Por Bisección)

Un algoritmo fundamental que exige que los datos estén ordenados. Funciona dividiendo repetidamente el intervalo de búsqueda a la mitad. Su complejidad temporal es logarítmica, O(log n), lo que lo hace extremadamente rápido para grandes volúmenes de datos ordenados.

// Versión iterativa, comúnmente utilizada
int busquedaBinaria(int datos[], int tamano, int clave) {
   int inicio = 0;
   int fin = tamano - 1;
   while (inicio <= fin) {
       // Calcula el punto medio de forma segura para prevenir desbordamiento
       int medio = inicio + (fin - inicio) / 2; 
       if (datos[medio] == clave) {
           return medio; // Clave encontrada
       } else if (datos[medio] < clave) {
           inicio = medio + 1; // Buscar en la mitad derecha
       } else {
           fin = medio - 1; // Buscar en la mitad izquierda
       }
   }
   return -1; // Clave no encontrada
}

3. Búsqueda por Interpolación

Esta técnica estima la posición del elemento basándose en el valor buscado y la distribución de los datos. La fórmula para calcular el índice medio es: medio = inicio + (clave - datos[inicio]) * (fin - inicio) / (datos[fin] - datos[inicio]). Es más eficiente que la búsqueda binaria cuando los datos están ordenados y distribuidos uniformemente. Sin embargo, puede ser más lenta que la binaria en casos de distribuciones de datos extremas.

4. Búsqueda por Fibonacci

Similar a la búsqueda binaria, utiliza la secuencia de Fibonacci para dividir el intervalo de búsqueda. El punto de división se basa en los números de Fibonacci. Aunque su lógica es interesante, su implementación no es tan común en entrevistas y se considera más para nichos específicos.

5. Búsqueda Hash

Utiliza una función hash para calcular directamente la posición del elemento, logrando una compeljidad temporal promedio de O(1). Es el método más rápido y funciona incluso con datos no ordenados. Las estructuras de datos como las tablas hash (implementadas en días anteriores) se basan en este principio.

Ejemplo de Prueba Completo

#include <stdio.h>

// Función de Búsqueda Secuencial
int busquedaSecuencial(int datos[], int tamano, int clave) {
   for (int i = 0; i < tamano; i++) {
       if (datos[i] == clave) return i;
   }
   return -1;
}

// Función de Búsqueda Binaria
int busquedaBinaria(int datos[], int tamano, int clave) {
   int inicio = 0, fin = tamano - 1;
   while (inicio <= fin) {
       int medio = inicio + (fin - inicio) / 2;
       if (datos[medio] == clave) return medio;
       else if (datos[medio] < clave) inicio = medio + 1;
       else fin = medio - 1;
   }
   return -1;
}

// Función auxiliar para imprimir resultados
void mostrarResultado(int posicion, int clave) {
   if (posicion != -1) {
       printf("Se encontró %d en el índice: %d\n", clave, posicion);
   } else {
       printf("No se encontró %d\n", clave);
   }
}

int main() {
   int conjuntoDatos[] = {1, 3, 5, 7, 9, 11, 13};
   int n = sizeof(conjuntoDatos)/sizeof(conjuntoDatos[0]);
   int valorBuscado = 7;

   mostrarResultado(busquedaSecuencial(conjuntoDatos, n, valorBuscado), valorBuscado);
   mostrarResultado(busquedaBinaria(conjuntoDatos, n, valorBuscado), valorBuscado);
   
   return 0;
}

Resultado de la ejecución:

Se encontró 7 en el índice: 3
Se encontró 7 en el índice: 3

Tabla Comparativa de Algoritmos de Búsqueda

Ejercicio Práctico

Dado el siguiente array ordenado: [2, 4, 6, 8, 10, 12, 14, 16]

1. Utiliza búsqueda binaria para encontrar el valor 10.
2. Utiliza búsqueda binaria para buscar el valor 5.
3. Muestra el índice encontrado o -1 si no se halla.