Búsqueda de interpolación

1. Algoritmo de búsqueda de interpolación
2. Ejemplo de búsqueda de interpolación
3. Implementación del algoritmo de búsqueda de interpolación
4. Complejidad del algoritmo de búsqueda de interpolación

La búsqueda por interpolación es un algoritmo de búsqueda rápido y eficiente. Mejora el algoritmo de búsqueda binaria para escenarios donde los elementos del array se distribuyen uniformemente sobre el array ordenada. Funciona en la posición de palpación del valor requerido. A diferencia de la búsqueda binaria, no siempre va a la mitad del array, pero puede ir a cualquier posición dependiendo del valor de la clave que se buscará. Comparamos el valor en la posición estimada y reducimos el espacio de búsqueda a la parte posterior o anterior. Por ejemplo, cuando buscamos una palabra en el diccionario, pasamos las páginas de acuerdo con la posición de las letras en su interior y no dividiendo el espacio de búsqueda en dos mitades cada vez.

Algoritmo de búsqueda de interpolación

Supongamos que tenemos un array sin clasificar A[] que contiene n elementos y queremos encontrar un elemento dado X.

Ejemplo de búsqueda de interpolación

Supongamos que tenemos el array (1, 3, 7, 8, 11, 15, 17, 18, 21), y queremos encontrar X - 18.

Implementación del algoritmo de búsqueda de interpolación

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X) {
  int lo = 0;
  int hi = n - 1;
  int mid;

  while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
    mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

    if (arr[mid] < X)
      lo = mid + 1;
    else if (X < arr[mid])
      hi = mid - 1;
    else
      return mid;
  }

  if (X == arr[lo])
    return lo;
  else
    return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int result = interpolation_search(arr, n, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Complejidad del algoritmo de búsqueda de interpolación

Complejidad del tiempo

• Caso promedio

La complejidad del tiempo de caso promedio del algoritmo es del orden de O(log (logn)). Ocurre cuando todos los elementos dentro del array se distribuyen uniformemente.

• Mejor caso

El mejor de los casos ocurre cuando el elemento que estamos buscando es el primer elemento sondeado por búsqueda de interpolación. La complejidad de tiempo del algoritmo en el mejor de los casos es O(1).

• Peor caso

El peor de los casos ocurre cuando los valores numéricos de los objetivos aumentan exponencialmente. La complejidad temporal del algoritmo en el peor de los casos es O(n).

Complejidad espacial

La complejidad espacial de este algoritmo es O(1) porque no requiere ninguna estructura de datos más que variables temporales.