Contenuto

• Tabella di comparazione
• Definizione di ricerca lineare
• Definizione di ricerca binaria
• Conclusione

La ricerca lineare e la ricerca binaria sono i due metodi utilizzati nelle matrici per ricerca gli elementi. La ricerca è un processo per trovare un elemento nell'elenco degli elementi memorizzati in qualsiasi ordine o in modo casuale.

La differenza principale tra ricerca lineare e ricerca binaria è che la ricerca binaria impiega meno tempo a 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 esiste un prerequisito per la ricerca binaria, ovvero gli elementi devono essere smistato mentre nella ricerca lineare non esiste tale prerequisito. Sebbene entrambi i metodi di ricerca utilizzino tecniche diverse che sono discusse di seguito.

1. Tabella di comparazione
2. Definizione
3. Differenze chiave
4. Conclusione

Tabella di comparazione

Base per il confronto	Ricerca lineare	Ricerca binaria
Complessità temporale	SU)	O (log 2 N)
Tempo migliore	Primo elemento O (1)	Center Element O (1)
Prerequisito per un array	Non richiesto	La matrice deve essere in ordine
Peggior caso per N numero di elementi	Sono richiesti N confronti	Può concludere solo dopo il log2N confronti
Può essere implementato su	Matrice e elenco collegato	Non può essere implementato direttamente nell'elenco collegato
Inserisci operazione	Inserito facilmente alla fine dell'elenco	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 senza necessità di elementi ordinati.	In ogni caso, gli algoritmi e gli elementi difficili dovrebbero essere organizzati in ordine.
Linee di codice	Di meno	Di Più

Definizione di ricerca lineare

In una ricerca lineare, ogni elemento di un array viene recuperato uno per uno in un ordine logico e verificato se è l'elemento desiderato o meno. Una ricerca avrà esito negativo se si accede a tutti gli elementi e l'elemento desiderato non viene trovato. Nel peggiore dei casi, il numero di un caso medio potrebbe essere necessario scansionare la 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 mediante la ricerca.

Efficienza di 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 effettuato un solo confronto. Quando il record desiderato è l'ultimo, è necessario effettuare 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 nel caso peggiore di questa tecnica è O (n) sta per l'ordine di esecuzione.

Programma C. per cercare un elemento con la tecnica di ricerca lineare.

#includere #includere void main () {int a, n, i, item, loc = -1; clrscr (); f (" nImmettere il numero di elementi:"); scanf ("% d", & n); f ("Inserisci i numeri: n"); per (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nImmettere il numero da cercare:"); scanf ("% d", & item); per (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; rompere; }} if (loc> = 0) {f (" n% d si trova nella posizione% d:", elemento, loc + 1); } else {f (" 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'oggetto dato nei confronti minimi possibili. Per eseguire la ricerca binaria, innanzitutto, dobbiamo ordinare gli elementi dell'array.

La logica alla base di questa tecnica è riportata di seguito:

• Innanzitutto, trova l'elemento centrale dell'array.
• L'elemento centrale dell'array viene confrontato con l'elemento da cercare.

Ci possono essere tre casi:

1. Se l'elemento è l'elemento richiesto, la ricerca ha esito positivo.
2. Quando l'elemento è inferiore all'elemento desiderato, cerca solo la prima metà dell'array.
3. Se è maggiore dell'elemento desiderato, cerca nella seconda metà dell'array.

Ripeti gli stessi passaggi fino a quando non viene trovato o esaurito un elemento nell'area di ricerca. In questo algoritmo, ogni volta che l'area di ricerca si riduce. 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.

Programma C. per trovare un elemento con la tecnica di ricerca binaria.

#includere void main () {int i, beg, end, middle, n, search, array; f ("Inserisci il numero dell'elemento n"); scanf ( "% d", & n); f ("Inserisci i% d numeri n", n); per (i = 0; i <n; i ++) scanf ("% d", & array); f ("Inserisci il numero da cercare n"); scanf ("% d", & search); beg = 0; fine = n - 1; middle = (beg + end) / 2; while (beg <= end) {if (array <ricerca) beg = middle + 1; altrimenti if (array == search) {f ("La ricerca ha esito positivo. n% d trovato nella posizione% d. n", ricerca, medio + 1); rompere; } else end = middle - 1; middle = (beg + end) / 2; } if (beg> end) f ("La ricerca non è riuscita!% d non è presente nell'elenco. n", cerca); getch (); }

1. La ricerca lineare è di natura iterativa e utilizza un approccio sequenziale. D'altra parte, la ricerca binaria implementa l'approccio di divisione e conquista.
2. La complessità temporale della ricerca lineare è O (N) mentre la ricerca binaria ha O (log₂N).
3. Il miglior tempo nella ricerca lineare è per il primo elemento, ovvero O (1). Al contrario, nella ricerca binaria, è per l'elemento centrale, cioè O (1).
4. Nella ricerca lineare, il caso peggiore per la ricerca di un elemento è il numero N di confronto. Al contrario, è log₂N numero di confronto per la ricerca binaria.
5. La ricerca lineare può essere implementata in un array o nell'elenco collegato, mentre la ricerca binaria non può essere implementata direttamente nell'elenco collegato.
6. Come sappiamo La ricerca binaria richiede l'array ordinato, motivo per cui 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 possono essere facilmente inseriti alla fine dell'elenco.
7. La ricerca lineare è facile da usare e non è necessario alcun elemento ordinato. D'altra parte, l'algoritmo di ricerca binaria è tuttavia complicato e gli elementi sono necessariamente disposti in ordine.

Conclusione

Gli algoritmi di ricerca lineare e binaria possono essere utili a seconda dell'applicazione. Quando un array è la struttura dei dati e gli elementi sono disposti in ordine, è preferibile la ricerca binaria Prestoricerca. Se l'elenco collegato è la struttura dei dati indipendentemente da come sono disposti gli elementi, la ricerca lineare viene adottata a causa dell'indisponibilità dell'implementazione diretta dell'algoritmo di ricerca binaria.

L'algoritmo di ricerca binaria tipico non può essere impiegato nell'elenco collegato perché l'elenco collegato è di natura dinamica e non è noto dove sia effettivamente assegnato l'elemento centrale. Pertanto, è necessario progettare la variazione dell'algoritmo di ricerca binaria che può funzionare anche sull'elenco collegato perché la ricerca binaria è più veloce nell'esecuzione di una ricerca lineare.