Estructura de datos: búsqueda de interpolación

La búsqueda por interpolación es una variante mejorada de la búsqueda binaria. Este algoritmo de búsqueda trabaja en la posición de sondeo del valor requerido. Para que este algoritmo funcione correctamente, la recopilación de datos debe estar ordenada y distribuida por igual.

La búsqueda binaria tiene una gran ventaja de complejidad temporal sobre la búsqueda lineal. La búsqueda lineal tiene la complejidad del peor de los casos de Ο (n) mientras que la búsqueda binaria tiene Ο (log n).

Hay casos en los que la ubicación de los datos objetivo puede conocerse de antemano. Por ejemplo, en el caso de una guía telefónica, si queremos buscar el número de teléfono de Morphius. Aquí, la búsqueda lineal e incluso la búsqueda binaria parecerá lenta, ya que podemos saltar directamente al espacio de memoria donde se almacenan los nombres que comienzan con 'M'.

Posicionamiento en búsqueda binaria

En la búsqueda binaria, si no se encuentran los datos deseados, el resto de la lista se divide en dos partes, inferior y superior. La búsqueda se realiza en cualquiera de ellos.

Incluso cuando los datos están ordenados, la búsqueda binaria no aprovecha para sondear la posición de los datos deseados.

Palpación de posición en la búsqueda de interpolación

La búsqueda de interpolación encuentra un elemento en particular calculando la posición de la sonda. Inicialmente, la posición de la sonda es la posición del elemento más intermedio de la colección.

Si se produce una coincidencia, se devuelve el índice del elemento. Para dividir la lista en dos partes, usamos el siguiente método:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

Si el elemento del medio es mayor que el elemento, la posición de la sonda se calcula nuevamente en la submatriz a la derecha del elemento del medio. De lo contrario, el elemento se busca en la submatriz a la izquierda del elemento del medio. Este proceso continúa también en la submatriz hasta que el tamaño de la submatriz se reduce a cero.

La complejidad en tiempo de ejecución del algoritmo de búsqueda de interpolación es Ο(log (log n)) en comparación con Ο(log n) de BST en situaciones favorables.

Algoritmo

Como es una improvisación del algoritmo BST existente, mencionamos los pasos para buscar el índice de valor de datos 'objetivo', utilizando el sondeo de posición:

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

Pseudocódigo

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Para conocer la implementación de la búsqueda por interpolación en el lenguaje de programación C, haga clic aquí .