Búsqueda exponencial

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

La búsqueda exponencial, también conocida como búsqueda duplicada o búsqueda con los dedos, es un algoritmo creado para buscar elementos en matrices de gran tamaño. Es un proceso de dos pasos. Primero, el algoritmo intenta encontrar el rango (L, R) en el que está presente el elemento objetivo y luego utiliza la búsqueda binaria dentro de este rango para encontrar la ubicación exacta del objetivo.

Se denomina búsqueda exponencial porque encuentra el elemento que contiene el rango buscando el primer exponente k para el que el elemento en el índice pow(2,k) es mayor que el objetivo. Aunque su nombre es búsqueda exponencial, la complejidad temporal de este algoritmo es logarítmica. Es muy útil cuando los Arrays son de tamaño infinito y convergen a una solución mucho más rápido que la búsqueda binaria.

Algoritmo de búsqueda exponencial

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

Ejemplo de búsqueda exponencial

Supongamos que tenemos el array: (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), y queremos encontrar X - 10.

Implementación del algoritmo de búsqueda exponencial

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

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int exponentialSearch(int arr[], int n, int x) {
  if (arr[0] == x) return 0;
  int i = 1;
  while (i < n && arr[i] <= x) i = i * 2;

  return binarySearch(arr, i / 2, min(i, n - 1), x);
}

int main() {
  int n = 11;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
  int x = 10;
  int result = exponentialSearch(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 exponencial

Complejidad del tiempo

• Caso promedio

La complejidad del tiempo de caso promedio es O(logi) donde i es el índice del elemento objetivo X dentro del array. Incluso supera a la búsqueda binaria cuando el elemento está cerca del comienzo del array.

• Mejor caso

El mejor de los casos ocurre cuando el elemento que comparamos es el elemento que estamos buscando y se devuelve en la primera iteración. La complejidad del tiempo en el mejor de los casos es O(1).

• Peor caso

La complejidad del tiempo del caso más desfavorable es la misma que la complejidad del tiempo del caso medio. La complejidad de tiempo en el peor de los casos es O(logi).

Complejidad espacial

La complejidad del espacio de este algoritmo es O(1) porque no requiere más espacio que las variables temporales.