Spiegazione degli algoritmi di ricerca lineare e binaria

La capacità di ricercare alcuni dati è un aspetto importante dell'informatica. Gli algoritmi di ricerca vengono utilizzati per cercare un particolare elemento in un set di dati.

Gli algoritmi restituiscono un risultato booleano (vero o falso) a una query di ricerca. Possono anche essere modificati per fornire la posizione relativa del valore trovato.

Per questo articolo, gli algoritmi si concentreranno sulla determinazione dell'esistenza di un valore.

Algoritmi di ricerca lineare

La ricerca lineare è anche nota come ricerca sequenziale. In questo tipo di ricerca, ogni valore in una lista viene visitato uno per uno in modo ordinato controllando se esiste il valore desiderato.

L'algoritmo controlla valore per valore finché non trova il valore che stai cercando o esaurisce i valori da cercare. Quando si esauriscono i valori per la ricerca, significa che la query di ricerca non esiste nell'elenco.

Un algoritmo di ricerca sequenziale accetta un elenco di valori e l'elemento desiderato nell'elenco come parametri. Il risultato restituito viene inizializzato come

falso e cambierà in Vero quando viene trovato il valore desiderato.

Vedi l'implementazione di Python di seguito come esempio:

def linearSearch (mylist, item):

trovato = falso

indice = 0

while index < len (mylist) e non trovato:

if mialista[indice] == articolo:

trovato = vero

altro:

indice = indice+1

ritorno trovato

Analisi dell'algoritmo

Lo scenario migliore si verifica quando l'elemento desiderato è il primo nell'elenco. Il caso peggiore si verifica quando l'elemento desiderato è l'ultimo dell'elenco (l'ennesimo elemento). Pertanto, la complessità temporale per la ricerca lineare è O(n).

Lo scenario di caso medio nell'algoritmo di cui sopra è n/2.

Relazionato: Che cos'è la notazione Big-O?

Ricerca lineare modificata

È importante sapere che l'algoritmo utilizzato presuppone che gli venga fornito un elenco casuale di elementi. Cioè, gli elementi dell'elenco non sono in un ordine particolare.

Supponiamo che gli elementi siano in un ordine particolare, diciamo dal più piccolo al più grande. Sarebbe possibile ottenere qualche vantaggio nel calcolo.

Prendi un esempio di ricerca di 19 nell'elenco dato: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Dopo aver raggiunto 23, diventerebbe chiaro che l'elemento cercato non esiste nell'elenco. Pertanto, non sarebbe più importante continuare a cercare il resto degli elementi dell'elenco.

Algoritmi di ricerca binaria

Hai visto come un elenco ordinato può ridurre il calcolo necessario. L'algoritmo di ricerca binaria sfrutta ancora di più questa efficienza rispetto a quella introdotta da un elenco ordinato.

L'algoritmo inizia prendendo un valore medio di un elenco ordinato e verificando se è il valore desiderato. In caso contrario, il valore viene controllato se è minore o maggiore del valore desiderato.

Se è inferiore, non è necessario controllare la metà inferiore dell'elenco. Altrimenti, se è maggiore, passa alla metà superiore dell'elenco.

Relazionato: Che cos'è la ricorsione e come si usa?

Indipendentemente dalla sottolista scelta (sinistra o destra), verrà nuovamente determinato il valore medio. Il valore viene nuovamente controllato se è il valore richiesto. In caso contrario, viene verificato se è minore o maggiore del valore richiesto.

Questo processo viene ripetuto finché non viene trovato un valore, se presente.

L'implementazione di Python di seguito è per l'algoritmo di ricerca binaria.

def binarySearch (mylist, item):

basso = 0

alto = len (mylist) - 1

trovato = falso

mentre basso <= alto e non trovato:

medio = (basso + alto) // 2

if mylist[mid] == item:

trovato = vero

elif item < mylist[mid]:

alto = medio - 1

altro:

basso = medio + 1

ritorno trovato

Analisi dell'algoritmo

Lo scenario migliore si verifica quando l'elemento desiderato è l'elemento centrale. Tuttavia, lo scenario peggiore non è così semplice. Segui l'analisi qui sotto:

Dopo il primo confronto, rimarranno n/2 elementi. Dopo il secondo, rimarranno n/4 elementi. Dopo il terzo, n/8.

Notare che il numero di elementi continua a dimezzarsi fino a raggiungere n/2i dove i è il numero di confronti. Dopo tutta la divisione, finiamo con un solo articolo.

Ciò implica:

n/2i=1

Pertanto, la ricerca binaria è O(log n).

Passando all'ordinamento

Nella ricerca binaria, abbiamo considerato un caso in cui l'array dato era già ordinato. Ma supponiamo di avere un set di dati non ordinato e di voler eseguire una ricerca binaria su di esso. Cosa faresti?

La risposta è semplice: ordinalo. Esistono numerose tecniche di ordinamento in informatica che sono state ben studiate. Una di queste tecniche che puoi iniziare a studiare è l'algoritmo di ordinamento della selezione, mentre abbiamo molte guide relative anche ad altre aree.

Come utilizzare l'ordinamento di selezione

L'ordinamento della selezione è un po' difficile da capire per i principianti, ma non è troppo impegnativo una volta che hai preso l'oscillazione delle cose.

Leggi Avanti

Circa l'autore