Algoritmo de búsqueda por interpolación (Interpolation Search)
1397
0
2025-08-02 18:47:29
Prohibida la reproducción sin autorización del autor
41
2
22
4
课程总结
收起全部章节
关闭课程总结
暂无课程总结
La búsqueda por interpolación es una mejora de la búsqueda binaria, que utiliza las leyes de distribución de datos para estimar la posición del valor objetivo, lo que puede ser más rápido que la búsqueda binaria, especialmente cuando los datos están distribuidos uniformemente.
🧠 Idea principal:
En un arreglo ordenado, si queremos buscar un valor x, en lugar de tomar siempre la posición central, es mejor estimar la posición probable basándose en la relación entre x y los valores de los extremos.
Fórmula de posición de interpolación:
mid = low + ((high - low) * (x - arr[low])) / (arr[high] - arr[low])
Esta fórmula es similar a la "interpolación de puntos en una recta numérica".
✅ Condiciones previas:
El arreglo debe estar ordenado de forma ascendente.
Los datos deben estar distribuidos aproximadamente de manera uniforme.
⏱️ Complejidad temporal:
Óptima: O(log log n) (más rápida que la búsqueda binaria)
Peor caso: O(n) (cuando los datos no son uniformes)
