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
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
/* 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
| Algoritmo | Complejidad temporal | Requiere orden | Escenario de aplicación |
|---|---|---|---|
| Búsqueda lineal | O(n) | no | Datos pequeños o desordenados |
| Búsqueda binaria | O(log n) | Sí | Arreglo ordenado, general y eficiente |
| Búsqueda por interpolación | O(log log n)Promedio | Sí | Escenarios específicos con distribución uniforme de datos |