Differenza tra ricerca binaria e ricerca lineare

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 una lista ordinata. Il metodo di ricerca binaria dimezza il numero di elementi controllati (in ciascuna 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 di un elenco in modo sequenziale 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 ricercato. L'output è true se l'elemento specificato è all'interno della sequenza fornita o false se non è presente nella sequenza. Poiché questo metodo controlla ogni elemento dell'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 facile da implementare.

Cos'è la ricerca binaria?

La ricerca binaria è anche un metodo utilizzato per localizzare un elemento specificato in una lista ordinata. Questo metodo inizia confrontando l'elemento cercato con gli elementi nel mezzo dell'elenco. Se il confronto determina che i due elementi sono uguali, il metodo si arresta 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 è inferiore all'elemento centrale, avvia nuovamente 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 con conseguente 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 funziona su elenchi ordinati, la ricerca di linea può operare anche su elenchi non ordinati. L'ordinamento di una lista ha generalmente una complessità del caso medio 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) prestazione del caso medio. D'altra parte, la ricerca binaria è considerata un metodo più efficiente che potrebbe essere utilizzato con elenchi di grandi dimensioni. Ma l'implementazione della ricerca binaria potrebbe essere abbastanza complicata e uno studio ha dimostrato che il codice esatto per la ricerca binaria può essere trovato solo in cinque su venti libri.