La principale differenza tra la ricerca lineare e la ricerca binaria è che la ricerca binaria richiede meno tempo per cercare un elemento dall'elenco ordinato di elementi. Quindi si deduce che l'efficienza del metodo di ricerca binaria è maggiore della ricerca lineare.
Un'altra differenza tra i due è che c'è un prerequisito per la ricerca binaria, cioè, gli elementi devono essere ordinati mentre nella ricerca lineare non esiste tale prerequisito. Sebbene entrambi i metodi di ricerca utilizzino tecniche diverse che vengono discusse di seguito.
Grafico comparativo
| Base per il confronto | Ricerca lineare | Ricerca binaria |
|---|---|---|
| Complessità del tempo | SOPRA) | O (log 2 N) |
| Miglior tempo di consegna | First Element O (1) | Center Element O (1) |
| Prerequisito per un array | Non richiesto | La matrice deve essere nell'ordine ordinato |
| Peggiore caso per N numero di elementi | N sono richiesti confronti | Si può concludere dopo aver confrontato solo 2 N di confronto |
| Può essere implementato su | Array e elenco collegato | Non può essere implementato direttamente nella lista collegata |
| Inserisci operazione | Facilmente inserito alla fine della lista | Richiede l'elaborazione da inserire nella posizione corretta per mantenere un elenco ordinato. |
| Tipo di algoritmo | Iterativo in natura | Dividi e conquista nella natura |
| Utilità | Facile da usare e nessuna necessità di elementi ordinati. | In ogni caso, l'algoritmo e gli elementi complicati dovrebbero essere organizzati in ordine. |
| Linee di codice | Di meno | Di Più |
Definizione di ricerca lineare
In una ricerca lineare, ogni elemento di una matrice viene recuperato uno alla volta in un ordine logico e controllato se si tratta di elemento desiderato o meno. Una ricerca non avrà successo se tutti gli elementi sono accessibili e l'elemento desiderato non viene trovato. Nel peggiore dei casi, il numero di un caso medio potrebbe essere necessario scansionare metà della dimensione dell'array (n / 2).
Pertanto, la ricerca lineare può essere definita come la tecnica che attraversa l'array in sequenza per individuare l'elemento specificato. Il programma riportato di seguito illustra la ricerca di un elemento dell'array tramite la ricerca.
Efficienza della ricerca lineare
Il consumo di tempo o il numero di confronti effettuati nella ricerca di un record in una tabella di ricerca determina l'efficienza della tecnica. Se il record desiderato è presente nella prima posizione della tabella di ricerca, viene eseguito un solo confronto. Quando il record desiderato è l'ultimo, devono essere effettuati n confronti. Se il record deve essere presentato da qualche parte nella tabella di ricerca, in media, il numero di confronti sarà (n + 1/2). L'efficienza peggiore di questa tecnica è O (n) l'ordine di esecuzione.
C Programma per cercare un elemento con tecnica di ricerca lineare.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nInserire il numero dell'elemento:"); scanf ("% d", & n); printf ("Inserire i numeri: \ n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nInserire il numero da cercare:"); scanf ("% d", & item); for (i = 0; i = 0) {printf ("\ n% d si trova nella posizione% d:", item, loc + 1); } else {printf ("\ n L'articolo non esiste"); } getch (); } Definizione di ricerca binaria
La ricerca binaria è un algoritmo estremamente efficiente. Questa tecnica di ricerca consuma meno tempo nella ricerca dell'elemento indicato in confronti minimi possibili. Per fare la ricerca binaria, innanzitutto, dobbiamo ordinare gli elementi dell'array.
Di seguito la logica alla base di questa tecnica:
- Innanzitutto, trova l'elemento centrale dell'array.
- L'elemento centrale dell'array viene confrontato con l'elemento da cercare.
Ci possono essere tre casi:
- Se l'elemento è l'elemento richiesto, la ricerca ha esito positivo.
- Quando l'elemento è inferiore all'elemento desiderato, cerca solo la prima metà dell'array.
- Se è maggiore dell'elemento desiderato, cerca nella seconda metà dell'array.
Ripeti gli stessi passaggi fino a quando un elemento viene trovato o esaurito nell'area di ricerca. In questo algoritmo, ogni volta che l'area di ricerca si sta riducendo. Pertanto il numero di confronti è al massimo log (N + 1). Di conseguenza, è un algoritmo efficiente rispetto alla ricerca lineare, ma l'array deve essere ordinato prima di eseguire la ricerca binaria.
C Programma per trovare un elemento con tecnica di ricerca binaria.
#include void main () {int i, beg, end, middle, n, search, array [100]; printf ("Inserire il numero dell'elemento \ n"); scanf ( "% d", & n); printf ("Inserire i% d numeri \ n", n); for (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Inserire il numero da cercare \ n"); scanf ("% d", & search); beg = 0; end = n - 1; medio = (inizio + fine) / 2; while (beg <= end) {if (array [middle] end) printf ("Ricerca fallita!% d non è presente nella lista. \ n", ricerca); getch (); } Differenze chiave tra ricerca lineare e ricerca binaria
- La ricerca lineare è di natura iterativa e utilizza un approccio sequenziale. D'altra parte, la ricerca binaria implementa l'approccio divide and conquer.
- La complessità temporale della ricerca lineare è O (N) mentre la ricerca binaria ha O (log 2 N).
- Il miglior tempo del caso nella ricerca lineare è per il primo elemento, ovvero, O (1). Come contro, nella ricerca binaria, è per l'elemento centrale, cioè, O (1).
- Nella ricerca lineare, il caso peggiore per la ricerca di un elemento è N numero di confronti. Al contrario, è log 2 N numero di confronto per la ricerca binaria.
- La ricerca lineare può essere implementata sia in una matrice che in una lista collegata, mentre la ricerca binaria non può essere implementata direttamente sulla lista collegata.
- Come sappiamo, la ricerca binaria richiede l'array ordinato che è la ragione. Richiede l'elaborazione da inserire nella posizione corretta per mantenere un elenco ordinato. Al contrario la ricerca lineare non richiede elementi ordinati, quindi gli elementi sono facilmente inseriti alla fine dell'elenco.
- La ricerca lineare è facile da usare e non è necessario alcun elemento ordinato. D'altra parte, l'algoritmo di ricerca binaria è comunque difficile, e gli elementi sono necessariamente disposti in ordine.
Conclusione
Gli algoritmi di ricerca lineare e binario possono essere utili a seconda dell'applicazione. Quando una matrice è la struttura dei dati e gli elementi sono disposti in ordine, allora la ricerca binaria è preferibile per la ricerca rapida . Se la lista dei collegamenti è la struttura dei dati indipendentemente da come sono disposti gli elementi, la ricerca lineare viene adottata a causa della non disponibilità dell'implementazione diretta dell'algoritmo di ricerca binaria.
L'algoritmo di ricerca binaria tipico non può essere utilizzato nella lista collegata perché la lista collegata è di natura dinamica e non è noto dove l'elemento centrale sia effettivamente assegnato. Quindi, c'è un requisito per progettare la variazione dell'algoritmo di ricerca binaria che può funzionare anche sulla lista collegata perché la ricerca binaria è più veloce in esecuzione di una ricerca lineare.
