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 necessario 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 è true se l'elemento specificato è all'interno della sequenza fornita o false se non è nella sequenza. Poiché questo metodo controlla ogni elemento nell'elenco fino a quando non viene trovato l'elemento specificato, nel peggiore dei casi esaminerà 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 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, riavvia il metodo utilizzando solo la metà inferiore dell'elenco ordinato. Se l'elemento cercato è inferiore all'elemento centrale, riavvia il metodo utilizzando solo la metà superiore dell'elenco ordinato. Se l'elemento cercato non è all'interno dell'elenco, il metodo restituirà un valore univoco che lo indica. Pertanto il metodo di ricerca binaria dimezza il numero di elementi confrontati (in ciascuna iterazione), a seconda del risultato del confronto. Di conseguenza, la ricerca binaria viene eseguita in tempo logaritmico risultando in o(log n) prestazioni medie del caso.
Qual è la differenza tra ricerca binaria e ricerca lineare?
Anche se sia la ricerca lineare che la ricerca binaria sono metodi di ricerca, presentano diverse differenze. Mentre la ricerca binaria opera su elenchi ordinati, la ricerca liner può operare anche su elenchi non ordinati. L'ordinamento di una lista ha generalmente una complessità media dei casi 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 della sua o(n) performance media dei casi. 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.
