Python - Algoritmos de búsqueda

La búsqueda es una necesidad muy básica cuando almacena datos en diferentes estructuras de datos. La evaluación más simple es revisar todos los elementos de la estructura de datos y relacionarlos con el valor que está buscando. Esto se conoce como búsqueda lineal. Es ineficiente y rara vez se usa, pero crear un programa para él da una idea de cómo podemos implementar algunos algoritmos de búsqueda avanzada.

Búsqueda lineal

En este tipo de búsqueda, se realiza una búsqueda secuencial de todos los elementos uno por uno. Se comprueba cada elemento y si se encuentra una coincidencia, se devuelve ese elemento en particular; de lo contrario, la búsqueda continúa hasta el final de la estructura de datos.

def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element	
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

Cuando se ejecuta el código anterior, produce el siguiente resultado:

True
False

Búsqueda de interpolación

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. 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. 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.

Existe una fórmula específica para calcular la posición media que se indica en el programa a continuación.

def intpolsearch(values,x ):
    idx0 = 0
    idxn = (len(values) - 1)

    while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point
	mid = idx0 +\
               int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
                    * ( x - values[idx0])))

# Compare the value at mid point with search value 
        if values[mid] == x:
            return "Found "+str(x)+" at index "+str(mid)

        if values[mid] < x:
            idx0 = mid + 1
    return "Searched element not in the list"


l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

Cuando se ejecuta el código anterior, produce el siguiente resultado:

Found 2 at index 0