Python - algorytmy wyszukiwania

Wyszukiwanie jest bardzo podstawową koniecznością, gdy przechowujesz dane w różnych strukturach danych. Najprościej jest przejść przez każdy element struktury danych i dopasować go do poszukiwanej wartości. Nazywa się to wyszukiwaniem liniowym. Jest nieefektywny i rzadko używany, ale stworzenie dla niego programu daje wyobrażenie o tym, jak możemy zaimplementować niektóre zaawansowane algorytmy wyszukiwania.

Wyszukiwanie liniowe

W przypadku tego typu wyszukiwania wyszukiwanie sekwencyjne obejmuje wszystkie elementy jeden po drugim. Każdy element jest sprawdzany i jeśli zostanie znaleziony pasujący element, zwracany jest ten konkretny element, w przeciwnym razie wyszukiwanie jest kontynuowane do końca struktury danych.

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

Wykonanie powyższego kodu daje następujący wynik -

True
False

Wyszukiwanie interpolacyjne

Ten algorytm wyszukiwania działa na pozycji sondowania wymaganej wartości. Aby ten algorytm działał prawidłowo, gromadzenie danych powinno być posortowane i równomiernie rozłożone. Początkowo pozycja sondy jest pozycją najbardziej środkowej pozycji kolekcji, a jeśli wystąpi dopasowanie, zwracany jest indeks pozycji. Jeśli środkowy element jest większy niż element, wówczas pozycja sondy jest ponownie obliczana w podtablicy na prawo od środkowego elementu. W przeciwnym razie element jest przeszukiwany w podtablicy po lewej stronie środkowego elementu. Ten proces jest kontynuowany również w pod macierzy, dopóki rozmiar podtablicy nie zmniejszy się do zera.

Istnieje specjalny wzór do obliczania pozycji środkowej, który jest wskazany w poniższym programie.

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

Wykonanie powyższego kodu daje następujący wynik -

Found 2 at index 0