Python - Ricerca di algoritmi

La ricerca è una necessità di base quando si archiviano dati in diverse strutture di dati. La valutazione più semplice è esaminare ogni elemento nella struttura dei dati e abbinarlo al valore che stai cercando. Questo è noto come ricerca lineare. È inefficiente e usato raramente, ma la creazione di un programma dà un'idea di come possiamo implementare alcuni algoritmi di ricerca avanzati.

Ricerca lineare

In questo tipo di ricerca, viene eseguita una ricerca sequenziale su tutti gli elementi uno per uno. Ogni elemento viene controllato e se viene trovata una corrispondenza, viene restituito quel particolare elemento, altrimenti la ricerca continua fino alla fine della struttura dei dati.

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 il codice sopra viene eseguito, produce il seguente risultato:

True
False

Ricerca in interpolazione

Questo algoritmo di ricerca funziona sulla posizione di rilevamento del valore richiesto. Affinché questo algoritmo funzioni correttamente, la raccolta dei dati deve essere in una forma ordinata e distribuita equamente. Inizialmente, la posizione della sonda è la posizione dell'elemento più centrale della raccolta. Se si verifica una corrispondenza, viene restituito l'indice dell'elemento. Se l'elemento centrale è maggiore dell'elemento, la posizione della sonda viene nuovamente calcolata nel sotto-array a destra dell'elemento centrale. In caso contrario, l'elemento viene cercato nel sottoarray a sinistra dell'elemento centrale. Questo processo continua anche sul sottoarray finché la dimensione del sottoarray non si riduce a zero.

Esiste una formula specifica per calcolare la posizione centrale che è indicata nel programma sottostante.

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 il codice sopra viene eseguito, produce il seguente risultato:

Found 2 at index 0