Algoritmos de búsqueda con Python: Búsqueda exponencial

Búsqueda exponencial

La búsqueda exponencial es útil para búsquedas ilimitadas, donde el tamaño de la matriz es infinito. En caso de que la búsqueda sea en una matriz limitada funciona mejor que la búsqueda binaria, sobre todo cuando el valor buscado esta al inicio del arreglo.

El algoritmo consiste en buscar un rango en el que sea más probable encontrar al valor buscado, donde se usará la búsqueda binaria.

En cada paso, el algoritmo compara el valor de búsqueda con el valor del índice $i$ de búsqueda actual. Si el elemento en el índice actual es más pequeño que el valor buscado, el algoritmo se repite, saltando al siguiente índice de búsqueda duplicándolo. Si el elemento en $i$ es mayor al elemento buscado, el algoritmo procederá a buscar en el intervalo comprendido entre $2^i$ y $2^{i+1}$.

Aplicaremos el algoritmo de búsqueda exponencial en la lista $[2,4,6,8,10,12]$ para buscar al elemento 6.

Algoritmo

1. Se verifica si el primer elemento de la lista coincide con el valor buscado: $lista[0]=2$, como el valor buscado es 6 se establece el indice $i=1$.
2. Recorriendo la lista y mientras i sea menor o igual al elemento buscado se multiplicará por dos:
1. $i = 1$, $lista[1] = 4$, que es menor que 6, entonces el índice es multiplicado por dos.
2. $i = 2$, $lista[2] = 6$, como es igual al valor buscado  es índice es multiplicado por dos.
3. $i = 4$, $lista[4] = 10$, como es mayor que 6 el ciclo se termina.
3. Se tiene una nueva lista que contiene a los elementos  hasta el cuarto elemento, donde se usará la búsqueda binaria.

1. Calculando el elemento medio: la semisuma de los índices mínimo y máximo, usando la división de enteros: $M=1$, el elemento del medio, $lista [1]= 4$ es diferente de 6.
2. Descartando elementos: Como la lista esta ordenada y por el algoritmo de la búsqueda binaria, se descarta mitad inferior, ya que los elementos que están antes del elemento del medio son menores que el buscado.

1. Calculando el nuevo elemento medio: $M = 2$, por lo que el elemento central se encuentra en el índice 2, $lista [2]= 6$ lo que coincide con elemento buscado.
2. Entonces se ha encontrado el elemento en el índice 2. Se devuelve el valor 2, concluyendo así con el algoritmo.

Implementación en Python

def BusquedaExponencial(lista, x):

    # Verificando si el primer elemento de la lista coincide
    # con el valor buscado
    if lista[0] == x:
        return 0
    i = 0

    # recorriendo los elementos de la lista,
    # y mientras el elemento en la posición i
    # es menor o igual al valor buscado,
    # aumenta exponencialmente el valor de i en múltiplos de dos:
    while i < len(lista) and lista[i] <= x:
        i = i * 2
        n = min(i, len(lista))

    return BusquedaBinaria(lista[0:n], x)

>>> BusquedaExponencial([2,4,6,8,10,12], 6)
2
>>>