Ricerca binaria vs ricerca lineare
La ricerca lineare, nota anche come ricerca sequenziale, è l'algoritmo di ricerca più semplice. Cerca un valore specificato in un elenco controllando ogni elemento nell'elenco. La ricerca binaria è anche un metodo utilizzato per individuare un valore specificato in un elenco ordinato. Il metodo di ricerca binaria dimezza il numero di elementi controllati (in ogni iterazione), riducendo il tempo impiegato per individuare l'elemento specificato nell'elenco.
Cos'è la ricerca lineare?
La ricerca lineare è il metodo di ricerca più semplice, che controlla ogni elemento in un elenco in sequenza finché non trova un elemento specificato. L'input per il metodo di ricerca lineare è una sequenza (come un array, una raccolta o una stringa) e l'elemento che deve essere cercato. L'output è vero se l'elemento specificato è all'interno della sequenza fornita o falso se non è nella sequenza. Poiché questo metodo controlla ogni elemento nell'elenco finché non viene trovato l'elemento specificato, nel peggiore dei casi passerà attraverso tutti gli elementi nell'elenco prima di trovare l'elemento richiesto. La complessità della ricerca lineare è o (n). Pertanto è considerato troppo lento per essere utilizzato durante la ricerca di elementi in elenchi di grandi dimensioni. Ma questo è molto semplice e più facile da implementare.
Cos'è la ricerca binaria?
La ricerca binaria è anche un metodo utilizzato per individuare un elemento specificato in un elenco ordinato. Questo metodo inizia confrontando l'elemento cercato con gli elementi al centro dell'elenco. Se il confronto determina che i due elementi sono uguali il metodo si interrompe e restituisce la posizione dell'elemento. Se l'elemento cercato è maggiore dell'elemento centrale, avvia nuovamente il metodo utilizzando solo la metà inferiore dell'elenco ordinato. Se l'elemento cercato è minore dell'elemento centrale, avvia nuovamente il metodo utilizzando solo la metà superiore dell'elenco ordinato. Se l'elemento cercato non è nell'elenco, il metodo restituirà un valore univoco che lo indica. Pertanto il metodo di ricerca binaria dimezza il numero di elementi confrontati (in ogni iterazione), a seconda del risultato del confronto. Di conseguenza,la ricerca binaria viene eseguita in tempo logaritmico con conseguente o (log n) prestazioni medie del caso.
Qual è la differenza tra la ricerca binaria e la ricerca lineare?
Sebbene sia la ricerca lineare che la ricerca binaria siano metodi di ricerca, presentano molte differenze. Mentre la ricerca binaria opera su elenchi ordinati, la ricerca lineare può funzionare anche su elenchi non ordinati. L'ordinamento di una lista ha generalmente una complessità media del caso di n log n. la ricerca lineare è semplice e diretta da implementare rispetto alla ricerca binaria. Tuttavia, la ricerca lineare è troppo lenta per essere utilizzata con elenchi di grandi dimensioni a causa delle prestazioni medie del case. D'altra parte, la ricerca binaria è considerata un metodo più efficiente che potrebbe essere utilizzato con elenchi di grandi dimensioni. Ma implementare la ricerca binaria potrebbe essere piuttosto complicato e uno studio ha dimostrato che il codice accurato per la ricerca binaria può essere trovato solo in cinque libri su venti.
