Python - Algoritmos de Pesquisa

Pesquisar é uma necessidade básica quando você armazena dados em diferentes estruturas de dados. A abordagem mais simples é percorrer todos os elementos da estrutura de dados e combiná-los com o valor que você está procurando. Isso é conhecido como pesquisa linear. É ineficiente e raramente usado, mas criar um programa para ele dá uma ideia de como podemos implementar alguns algoritmos de pesquisa avançados.

Pesquisa Linear

Nesse tipo de busca, uma busca sequencial é feita em todos os itens um a um. Cada item é verificado e se uma correspondência for encontrada, esse item em particular é retornado, caso contrário, a pesquisa continua até o final da estrutura de dados.

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

Quando o código acima é executado, ele produz o seguinte resultado -

True
False

Pesquisa de interpolação

Este algoritmo de pesquisa funciona na posição de sondagem do valor necessário. Para que esse algoritmo funcione corretamente, a coleta de dados deve ser ordenada e igualmente distribuída. Inicialmente, a posição da sonda é a posição do item mais intermediário da coleção. Se ocorrer uma correspondência, o índice do item será retornado. Se o item do meio for maior do que o item, a posição da sonda é calculada novamente na submatriz à direita do item do meio. Caso contrário, o item é pesquisado na submatriz à esquerda do item do meio. Este processo continua na submatriz também até que o tamanho da submatriz seja reduzido a zero.

Existe uma fórmula específica para o cálculo da posição intermediária indicada no programa abaixo.

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

Quando o código acima é executado, ele produz o seguinte resultado -

Found 2 at index 0