Interpolation Search

Definición: Busca en un arreglo ordenado mediante estimación de la posición siguiente, para comprobar sobre la base de una interpolación lineal de la clave de búsqueda y los valores en los valores en los extremos del intervalo buscado.

• Cuando buscamos un nombre en la agenda telefónica, no comenzamos del medio , Iniciamos de la letra base de la persona a buscar.
• Esta es la idea principal para el interpolation search.
• En una búsqueda binaria, simplemente usamos el medio de una lista ordenada como la mejor estimación donde se iniciara la búsqueda.
• Ahora usaremos una interpolación que involucra ala clave, el comienzo de la lista y el final. i=(k-l[0]) /(l[n-1]-l[0])*n
• Cuando buscamos “15” en: 0 4 5 9 10 12 15 20 ==> i=((15-0)/(20-0))*8 ==> i=6
• Su complejidad es O(log log n) asumiendo que las claves son uniformemente distribuidas. Y en el peor para cualquier distribucion es O(n).

Algorithm (Algoritmo)

• func interpolation_search(list A, integer numer){
  
  integer low=1,high=A.size,mid;
  
  while(list[low]=numer){
  
  mid=low + ((numer-list[low])*(high-low))/(list[high]-list[low]);
  
  if(list[mid]
  
  else if(list[mid]>numer) high=mid-1;
  
  else low=mid;
  
  }
  
  if(list[low]==numer)
  
  return low;
  
  else return 0;
  
  }

En este link adjunto su codigo en C++, los valores del vector se cargan mediante el file numbers.in.