La búsqueda por interpolación funciona mejor que la búsqueda binaria para una array ordenada y distribuida uniformemente .
La búsqueda binaria va al elemento central para verificar independientemente de la clave de búsqueda. Por otro lado, la búsqueda de interpolación puede ir a diferentes ubicaciones según la clave de búsqueda. Si el valor de la clave de búsqueda está cerca del último elemento, es probable que la búsqueda de interpolación comience la búsqueda hacia el lado final.
En promedio, la búsqueda por interpolación hace comparaciones de log(log(n)) (si los elementos están distribuidos uniformemente), donde n es el número de elementos que se buscarán. En el peor de los casos (por ejemplo, cuando los valores numéricos de las teclas aumentan exponencialmente), puede hacer comparaciones de hasta O(n).
Artículo de búsqueda de interpolación
Fuentes:
http://en.wikipedia.org/wiki/Interpolation_search
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA