Prima di comprendere le differenze tra la ricerca lineare e quella binaria, dovremmo prima conoscere separatamente la ricerca lineare e la ricerca binaria.
Cos'è una ricerca lineare?
Una ricerca lineare è anche nota come ricerca sequenziale che analizza semplicemente ciascun elemento alla volta. Supponiamo di voler cercare un elemento in un array o in una lista; calcoliamo semplicemente la sua lunghezza e non saltiamo su nessun elemento.
Consideriamo un semplice esempio.
Supponiamo di avere un array di 10 elementi come mostrato nella figura seguente:
La figura sopra mostra un array di tipi di carattere con 10 valori. Se vogliamo cercare 'E', la ricerca inizia dallo 0thelemento ed esegue la scansione di ogni elemento finché l'elemento, ovvero 'E', non viene trovato. Non possiamo saltare direttamente dallo 0thelemento al 4thelemento, ovvero ogni elemento viene scansionato uno per uno finché non viene trovato.
Complessità della ricerca lineare
Poiché la ricerca lineare esegue la scansione di ciascun elemento uno per uno finché l'elemento non viene trovato. Se il numero di elementi aumenta, aumenta anche il numero di elementi da scansionare. Possiamo dire che il il tempo impiegato per la ricerca degli elementi è proporzionale al numero di elementi . Pertanto, la complessità del caso peggiore è O(n)
Cos'è una ricerca binaria?
Una ricerca binaria è una ricerca in cui viene calcolato l'elemento centrale per verificare se è più piccolo o più grande dell'elemento da cercare. Il vantaggio principale dell'utilizzo della ricerca binaria è che non esegue la scansione di ogni elemento dell'elenco. Invece di scansionare ogni elemento, esegue la ricerca fino a metà dell'elenco. Pertanto, la ricerca binaria impiega meno tempo per cercare un elemento rispetto a una ricerca lineare.
L'unico prerequisito della ricerca binaria è che un array dovrebbe essere ordinato, mentre la ricerca lineare funziona sia su array ordinati che non ordinati. L'algoritmo di ricerca binaria si basa sulla tecnica “divide et impera”, ovvero dividerà l'array in modo ricorsivo.
Ci sono tre casi utilizzati nella ricerca binaria:
Caso 1: dati
Caso 2: dati>a[mid] quindi destra=mid-1
Caso 3: data = a[mid] // l'elemento viene trovato
Nel caso di cui sopra, ' UN ' è il nome dell'array, metà è l'indice dell'elemento calcolato ricorsivamente, dati è l'elemento da cercare, Sinistra denota l'elemento sinistro dell'array e Giusto denota l'elemento che si trova sul lato destro dell'array.
Capiamo il funzionamento della ricerca binaria attraverso un esempio.
Supponiamo di avere un array di 10 dimensioni indicizzato da 0 a 9 come mostrato nella figura seguente:
Vogliamo cercare 70 elementi dall'array sopra.
Passo 1: Per prima cosa calcoliamo l'elemento centrale di un array. Consideriamo due variabili, cioè sinistra e destra. Inizialmente, sinistra = 0 e destra = 9 come mostrato nella figura seguente:
Il valore dell'elemento centrale può essere calcolato come:
Pertanto mid = 4 e a[mid] = 50. L'elemento da cercare è 70, quindi a[mid] non è uguale a data. Il caso 2 è soddisfatto, ovvero data>a[mid].
Passo 2: Poiché data>a[mid], quindi il valore di left viene incrementato di mid+1, ovvero left=mid+1. Il valore di mid è 4, quindi il valore di left diventa 5. Ora abbiamo un sottoarray come mostrato nella figura seguente:
Ancora una volta, il valore medio viene calcolato utilizzando la formula precedente e il valore medio diventa 7. Ora, il valore medio può essere rappresentato come:
Nella figura sopra, possiamo osservare che a[mid]>data, quindi, ancora una volta, il valore di mid verrà calcolato nel passaggio successivo.
Passaggio 3: Come a[mid]>data, il valore di right viene diminuito di mid-1. Il valore di mid è 7, quindi il valore di right diventa 6. L'array può essere rappresentato come:
Il valore di mid verrà calcolato nuovamente. I valori di sinistra e destra sono rispettivamente 5 e 6. Pertanto, il valore di mid è 5. Ora mid può essere rappresentato in un array come mostrato di seguito:
Nella figura sopra, possiamo osservare che a[mid]
Passaggio 4: Come [metà] Ora il valore di mid viene calcolato nuovamente utilizzando la formula di cui abbiamo già discusso. I valori di left e right sono rispettivamente 6 e 6, quindi il valore di mid diventa 6 come mostrato nella figura seguente: Possiamo osservare nella figura sopra che a[mid]=data. Pertanto, la ricerca è completata e l'elemento viene trovato correttamente. Di seguito sono riportate le differenze tra ricerca lineare e ricerca binaria: Descrizione La ricerca lineare è una ricerca che trova un elemento nell'elenco cercando l'elemento in sequenza finché l'elemento non viene trovato nell'elenco. D'altra parte, una ricerca binaria è una ricerca che trova ricorsivamente l'elemento centrale nell'elenco finché l'elemento centrale non viene abbinato a un elemento cercato. Funzionamento di entrambe le ricerche La ricerca lineare inizia la ricerca dal primo elemento ed esegue la scansione di un elemento alla volta senza passare all'elemento successivo. D'altro canto, la ricerca binaria divide l'array a metà calcolando l'elemento centrale dell'array. Implementazione La ricerca lineare può essere implementata su qualsiasi struttura dati lineare come vettore, lista concatenata singola, lista concatenata doppia. Al contrario, la ricerca binaria può essere implementata su quelle strutture dati con attraversamento bidirezionale, cioè attraversamento in avanti e all'indietro. Complessità La ricerca lineare è facile da usare, o possiamo dire che è meno complessa in quanto gli elementi per una ricerca lineare possono essere disposti in qualsiasi ordine, mentre in una ricerca binaria gli elementi devono essere disposti in un ordine particolare. Elementi ordinati Gli elementi per una ricerca lineare possono essere disposti in ordine casuale. Nella ricerca lineare non è obbligatorio che gli elementi siano disposti in ordine ordinato. In una ricerca binaria, invece, gli elementi devono essere disposti in ordine ordinato. Può essere organizzato in ordine crescente o decrescente e di conseguenza l'algoritmo verrà modificato. Poiché la ricerca binaria utilizza un array ordinato, è necessario inserire l'elemento nella posizione corretta. Al contrario, la ricerca lineare non necessita di un array ordinato, in modo che il nuovo elemento possa essere facilmente inserito alla fine dell'array. Approccio La ricerca lineare utilizza un approccio iterativo per trovare l'elemento, quindi è anche nota come approccio sequenziale. Al contrario, la ricerca binaria calcola l'elemento centrale dell'array, quindi utilizza l'approccio divide et impera. Insieme di dati La ricerca lineare non è adatta per un set di dati di grandi dimensioni. Se vogliamo cercare l'elemento, che è l'ultimo elemento dell'array, una ricerca lineare inizierà la ricerca dal primo elemento e proseguirà fino all'ultimo elemento, quindi il tempo impiegato per cercare l'elemento sarebbe lungo. D'altra parte, la ricerca binaria è adatta per un set di dati di grandi dimensioni poiché richiede meno tempo. Velocità Se il set di dati è ampio nella ricerca lineare, il costo computazionale sarebbe elevato e la velocità diventerebbe lenta. Se il set di dati è ampio nella ricerca binaria, il costo computazionale sarebbe inferiore rispetto a una ricerca lineare e la velocità diventerebbe elevata. Dimensioni La ricerca lineare può essere utilizzata sia su array monodimensionali che multidimensionali, mentre la ricerca binaria può essere implementata solo su array unidimensionali. Efficienza La ricerca lineare è meno efficiente se consideriamo i grandi set di dati. La ricerca binaria è più efficiente della ricerca lineare nel caso di insiemi di dati di grandi dimensioni. Diamo un'occhiata alle differenze in forma tabellare. 
Differenze tra ricerca lineare e ricerca binaria
costruttore Python
Base di confronto Ricerca lineare Ricerca binaria Definizione La ricerca lineare inizia la ricerca dal primo elemento e confronta ciascun elemento con un elemento cercato finché l'elemento non viene trovato. Trova la posizione dell'elemento cercato trovando l'elemento centrale dell'array. Dati ordinati In una ricerca lineare, non è necessario disporre gli elementi in ordine ordinato. Il presupposto per la ricerca binaria è che gli elementi siano disposti in ordine ordinato. Implementazione La ricerca lineare può essere implementata su qualsiasi struttura dati lineare come un array, un elenco collegato, ecc. L'implementazione della ricerca binaria è limitata in quanto può essere implementata solo su quelle strutture dati che hanno attraversamento bidirezionale. Approccio Si basa sull'approccio sequenziale. Si basa sull’approccio divide et impera. Misurare È preferibile per i set di dati di piccole dimensioni. È preferibile per i set di dati di grandi dimensioni. Efficienza È meno efficiente nel caso di set di dati di grandi dimensioni. È più efficiente nel caso di set di dati di grandi dimensioni. Nella peggiore delle ipotesi In una ricerca lineare, lo scenario peggiore per trovare l'elemento è O(n). In una ricerca binaria, lo scenario peggiore per trovare l'elemento è O(log2N). Scenario migliore In una ricerca lineare, lo scenario migliore per trovare il primo elemento nell'elenco è O(1). In una ricerca binaria, lo scenario migliore per trovare il primo elemento nell'elenco è O(1). Matrice dimensionale Può essere implementato sia su un array monodimensionale che multidimensionale. Può essere implementato solo su un array multidimensionale.