Algoritmos de búsqueda con Python - Parte I

La búsqueda de datos forma parte de muchos procesos de computación, por ejemplo, consiste en encontrar un elemento determinado en un conjunto finito de datos, y la posición que ocupa. 

Python cuenta con una función básica de búsqueda, la función index(); que devuelve la posición del elemento buscado en caso se encuentre en la lista. Previamente se puede averiguar si el elemento se encuentra o no en la lista con el comando in que devuelve un valor booleano.

>>> 'y' in 'j,u,p,y,t,e,r']
True
>>> ['j','u','p',y','t','e','r'].index('y')
3
>>>

De lo contrario devuelve un mensaje de error.

>>> ['j','u','p',y','t','e','r'].index('a')
Traceback (most recent call last):
  File "", line 1, in <module> 
ValueError: 'a' is not in list
>>>

El proceso anterior tiene un costo computacional que puede ser reducido con un algoritmo adecuado, para ello hay muchos que son más rápidos y/o eficientes , además de que aprovechan la disposición de los datos.

Búsqueda lineal o secuencial:

Es el método más sencillo y se puede ver como una versión progresiva del operador in(). El algoritmo consiste en comparar los elementos de una matriz con el elemento de búsqueda, y una vez encontrado se devuelve el índice de su primera aparición.

def BusquedaLinea(lista,x):
    # Función que busca x en lista y devuelve su posición
    # Si no encuentra el elemento, devuelve -1
    i = 0
    for j in lista:
        if lista[j] == x:
            return i
        else:
            i = i + 1
    return -1

>>> BusquedaLineal(['c','c++','java','python'],'java')
2
>>>
>>> BusquedaLineal([1,3,5,8,13],2)
-1

No es tan rápida ni eficiente como otros algoritmos de búsqueda, pero es útil con arreglos pequeños y no ordenados.

Búsqueda binaria o dicotómica:

Este algoritmo funciona eficientemente con arreglos grandes y ordenados, consiste en eliminar tras cada comparación la mitad de los elementos del arreglo en los que se efectúa la búsqueda; teniendo en cuenta los criterios:

• Si el elemento buscado es menor que el elemento medio, entonces el elemento está en la mitad inferior de la tabla.
• Si es mayor es porque el elemento está en la mitad superior.
• Si el elemento es igual se finaliza con a búsqueda.

def BusquedaBinaria(lista,x):
    inicio = 0 
    fin = len(lista) - 1
 
    while inicio <= fin:
        # Verificando el punto medio
        medio = (inicio + fin)/2
        if lista[medio] == x:
        # Si es el valor buscado devuelve el indice
            return medio

        # Si el valor central es mayor al buscado
        elif lista[medio] > x:
            fin = medio -1

        # Si el valor central es menor al buscado
        else:
            inicio = medio + 1

    return -1

>>> BusquedaBinaria(['c','c++','java','python'],'python')
3
>>>

Búsqueda por saltos

Se usa en arreglos ordenados y combina las utilidades de la búsqueda binaria y lineal. En lugar de buscar en todo el arreglo de forma secuencial, lo hace en segmentos determinados por un salto u omite algunos elementos.

Cuando el salto usado es 1, el algoritmo es la búsqueda lineal tradicional, el valor óptimo del salto es la raíz del rango de la matriz, así se evaluarán los elementos: lista[0], lista[0 + salto], lista[0 + 2salto], lista[0 + 3salto] con la búsqueda lineal. 

import math

def BusquedaPorSalto(lista, x):
   h = len(lista)
 
    # Determinar el salto
    salto = int(math.sqrt(h))
    y, minimo = 0, 0

 
    for j in lista:
        if lista[j] == x:
            return i
        else:
            i = i + 1
    return -1

>>> BusquedaPorSalto(['c','c++','java','matlab','python'],'python')
4
>>>

Búsqueda Fibonacci
 Una mejora de la búsqueda binaria es no usar el elemento medio en cada paso, sino dividir el arreglo en dos partes  de tamaños que son numeros de Fibonacci y buscar en el que sea mas probable encontrar el valor buscado.

Veamos el algoritmo e implementación:

import math

def BusquedaDeFibonacci:
    f2 = 0
    f1 = 1
    f2 = f1 + f2
 
    # se encuentra el número de Fibonacci más pequeño mayor o igual que número de elementos en la matriz de búsqueda que va ser f3
    while (f3 < len(lista)):
    f2 = f1,
    f1 = f3,
    f3 = f1 + f2,
    #numero Fibonacci que indica la posicion del Fibonacci que corresponde a la posicion de la lista, 0

 
    i = -1;
    # verificamos el elemento lista[j]donde j es el mínimo entre i + f2 y (len(lista)-1)) . ;
    while (f3 > 1):
        j = min(i + f2, (len(lista)-1))
    # si el valor es más pequeño que el valor buscado ;
    # movemos los números de Fibonacci un paso hacia abajo en la secuencia;
        if (lista[j] < x):
            f3 = f1
            f1 = f2
            f2 = f3 - f1
            i = j
    # caso contrario, se muevemen los números de Fibonacci dos pasos hacia abajo en la secuencia;
        elif (lista[j] > x):
            f3 = f2
            f1 = f1 - f2
            f2 = f3 - f1
        else :
            return j
    if(f1 and i < (len(lista)-1) and lista[i+1] == x):
        return i+1;
    return -1

>>> BusquedaDeFibonacci([1,2,3,4,5,6,7,8,9], 17)
-1
>>>