Differenza tra ricerca lineare e binaria in informatica

Ricerca lineare

In informatica, la ricerca lineare, in inglese Linear search, nota anche come ricerca sequenziale, è l’algoritmo di ricerca più semplice che cerca un elemento in un elenco in ordine sequenziale. Si basa sulla tecnica di attraversare un elenco dall’inizio alla fine esplorando le proprietà di tutti gli elementi che si trovano sulla strada. La ricerca lineare è per lo più molto semplice da implementare ed è pratica quando l’elenco contiene solo pochi elementi o quando si esegue una singola ricerca in un elenco non ordinato (elenco in cui gli elementi non sono ordinati).

La ricerca lineare viene implementata utilizzando i seguenti passaggi:

Passaggio 1: leggere l’elemento di ricerca dall’utente

Passaggio 2: Confronta l’elemento di ricerca con il primo elemento nell’elenco.

Passaggio 3: se entrambi corrispondono, visualizzare ” dato elemento trovato ” e terminare la funzione.

Passaggio 4: se entrambi non corrispondono, confronta l’elemento di ricerca con l’elemento successivo nell’elenco.

Passaggio 5: Ripetere i passaggi 3 e 4 fino a quando l’elemento di ricerca non viene confrontato con l’ultimo elemento nell’elenco.

Passaggio 6: se anche l’ultimo elemento nell’elenco non corrisponde, visualizzare “Elemento non trovato” e terminare la funzione.

Ricerca binaria

La ricerca binaria, in inglese binary search, è un algoritmo efficiente per trovare un elemento da un elenco ordinato di elementi. Funziona dividendo ripetutamente a metà la porzione dell’elenco che potrebbe contenere l’elemento, fino a quando non hai ristretto le posizioni possibili a una sola. Uno dei modi più comuni per utilizzare la ricerca binaria è trovare un elemento in un array ordinato o in un elenco di grandi dimensioni. La complessità del tempo lo rende molto veloce rispetto ad altri algoritmi di ordinamento.

L’algoritmo di ricerca binaria funziona sul principio del divide et impera. Uno dei principali limiti della ricerca binaria è che l’array o l’elenco di elementi deve essere ordinato affinché l’algoritmo funzioni su di esso.

La ricerca binaria cerca un elemento particolare confrontando l’elemento più centrale della raccolta. Se si verifica una corrispondenza, viene restituito l’indice dell’elemento. Se l’elemento centrale è maggiore dell’elemento, l’elemento viene cercato nel sotto-array a sinistra dell’elemento centrale. In caso contrario, l’elemento viene cercato nel sotto-array a destra dell’elemento centrale. Questo processo continua anche sull’array secondario finché la dimensione del sotto-array non si riduce a zero.

Differenza tra ricerca lineare e ricerca binaria

BASE DI CONFRONTO	RICERCA LINEARE	RICERCA BINARIA
Descrizione	La ricerca lineare è un algoritmo per trovare un elemento in una lista controllando in sequenza gli elementi della lista fino a trovare l’elemento corrispondente.	La ricerca binaria è un algoritmo che trova la posizione di un valore target all’interno di un array ordinato.
Come funziona	Una ricerca lineare esegue la scansione di un elemento alla volta senza saltare a nessun elemento.	Una ricerca binaria riduce della metà la ricerca non appena viene trovata la metà di un elenco ordinato.
Implementazione	Le ricerche lineari possono essere implementate su qualsiasi contenitore lineare (vettore, lista singola collegata, doppia lista collegata).	Le ricerche binarie possono essere implementate solo su strutture dati in cui è possibile l’attraversamento bidirezionale.
Complessità	La ricerca lineare è facile da usare perché non è necessario alcun elemento ordinato.	La ricerca binaria è un po ‘complicata con gli elementi che sono necessariamente disposti in un dato ordine.
Elementi ordinati	La ricerca lineare nel linguaggio di programmazione C non richiede gli elementi ordinati quindi gli elementi sono convenientemente inseriti in fondo alla lista.	Una ricerca binaria nel linguaggio di programmazione C richiede array ordinati per prestazioni efficaci. Ciò facilita l’inserimento di elementi nella posizione richiesta e, in sostanza, il mantenimento di elenchi ordinati.
Approccio	La ricerca lineare è ripetitiva o iterativa e utilizza l’approccio sequenziale nella sua funzionalità.	La ricerca binaria utilizza l’approccio divide et impera nella sua funzionalità.
Prestazione	Nella ricerca lineare, le prestazioni sono ottenute mediante confronti di uguaglianza.	Nella ricerca binaria, le prestazioni vengono eseguite ordinando i confronti.
Scenario peggiore	Nella ricerca lineare, lo scenario peggiore per la ricerca di un elemento è equivalente al numero di confronto O (n) .	Nella ricerca binaria, lo scenario peggiore è O (Log 2 n) numero di somiglianze.
Scenario del miglior caso	Lo scenario migliore in una ricerca lineare è trovare l’elemento nella prima posizione O (1).	Lo scenario migliore è trovare l’elemento nella posizione centrale O (1).
Complessità temporale	La complessità temporale della ricerca lineare sembra essere O (n).	La complessità temporale della ricerca binaria è O (log 2 n).