Algoritmo di ricerca binaria: funzione, vantaggi, complessità temporale e spaziale

introduzione

In qualsiasi sistema computazionale, la ricerca è una delle funzionalità più critiche da sviluppare. Le tecniche di ricerca vengono utilizzate nel recupero di file, nell'indicizzazione e in molte altre applicazioni. Ci sono molte tecniche di ricerca disponibili. Uno dei quali è la tecnica di ricerca binaria.

Un algoritmo di ricerca binaria lavora sull'idea di trascurare metà dell'elenco ad ogni iterazione. Continua a dividere l'elenco finché non trova il valore che sta cercando in un determinato elenco. Un algoritmo di ricerca binaria è un rapido aggiornamento a un semplice algoritmo di ricerca lineare.

Nessuna esperienza di codifica richiesta. Supporto professionale a 360°. Diploma PG in Machine Learning e AI da IIIT-B e upGrad.

Utilizzo di un algoritmo di ricerca binaria

La prima cosa da notare è che un algoritmo di ricerca binaria funziona sempre su un elenco ordinato. Quindi il primo passo logico è ordinare l'elenco fornito. Dopo l'ordinamento, la mediana dell'elenco viene verificata con il valore desiderato.

• Se il valore desiderato è uguale al valore dell'indice centrale, l'indice viene restituito come risposta.

• Se il valore target è inferiore al deal dell'indice centrale dell'elenco, il lato destro dell'elenco viene ignorato.

• Se il valore desiderato è maggiore del valore dell'indice centrale, la metà sinistra viene scartata.

• Il processo viene quindi ripetuto su elenchi abbreviati finché non viene trovato il valore target.

Esempio 1

Esaminiamo l'algoritmo con un esempio. Supponiamo che ci sia una lista con i seguenti numeri:

1, 15, 23, 7, 6, 14, 8, 3, 27

Prendiamo il valore desiderato come 27. Il numero totale di elementi nell'elenco è 9.

Il primo passo è ordinare l'elenco. Dopo l'ordinamento, l'elenco sarebbe simile a questo:

1, 3, 6, 7, 8, 14, 15, 23, 27

Poiché il numero di elementi nell'elenco è nove, l'indice centrale sarebbe a cinque. Il valore all'indice cinque è 8. Il valore desiderato, 27, viene confrontato con il valore 8. Innanzitutto, controlla se il valore è uguale a 8 o meno. Se sì, restituisce index ed esci.

Poiché 27 è maggiore di 8, ignoreremmo la parte sinistra e attraverseremo solo il lato destro dell'elenco. La nuova lista da percorrere è:

14, 15, 23, 27

Nota: in pratica, l'elenco non viene troncato. Solo l'osservazione è ristretta. Quindi, la "nuova lista" non deve essere confusa con la creazione di una nuova lista o l'abbreviazione di quella originale. Sebbene possa essere implementato con un nuovo elenco, ci sono due problemi. Innanzitutto, ci sarà un sovraccarico di memoria. Ogni nuovo elenco aumenterà la complessità dello spazio. E in secondo luogo, gli indici originali devono essere monitorati a ogni iterazione.

Il nuovo indice centrale può essere preso come secondo o terzo elemento, a seconda dell'implementazione. Qui consideriamo centrale il terzo elemento. Il valore 23 viene confrontato con il valore 27. Poiché il valore è maggiore del valore centrale, scarteremo la metà sinistra.

La lista da percorrere è:

27

Poiché l'elenco contiene un solo elemento, è considerato l'elemento centrale. Quindi, confrontiamo il valore desiderato con 27. Quando corrispondono, restituiamo il valore dell'indice di 27 nell'elenco originale.

Esempio #2

Nella stessa lista, assumiamo che il valore desiderato sia 2.

Innanzitutto, il valore centrale otto viene confrontato con 2. Poiché il valore desiderato è inferiore al valore centrale, restringiamo la nostra attenzione al lato sinistro dell'elenco.

La nuova traversata sarà composta da:

1, 3, 6, 7

Prendiamo l'elemento centrale come secondo elemento. Il valore desiderato due viene confrontato con 3. Poiché il valore è ancora più piccolo, restringiamo nuovamente lo stato attivo sul lato sinistro dell'elenco.

La nuova traversata sarà composta da:

1

Poiché la lista di attraversamento ha un solo elemento, il valore viene confrontato direttamente con l'elemento rimanente. Vediamo che i valori non corrispondono. Quindi, usciamo dal ciclo con un messaggio di errore: v alue not found .

Certificazione avanzata di data science, oltre 250 partner di assunzione, oltre 300 ore di apprendimento, 0% EMI

Complessità del tempo e dello spazio

La complessità temporale dell'algoritmo di ricerca binaria è O(log n). La complessità temporale del caso migliore sarebbe O(1) quando l'indice centrale corrisponderebbe direttamente al valore desiderato. Lo scenario peggiore potrebbe essere i valori alle estremità dell'elenco o valori non presenti nell'elenco.

La complessità spaziale dell'algoritmo di ricerca binaria dipende dall'implementazione dell'algoritmo. Ci sono due modi per implementarlo:

1. Metodo iterativo
2. Metodo ricorsivo

Entrambi i metodi sono praticamente gli stessi, con due differenze nell'implementazione. Innanzitutto, non esiste un ciclo nel metodo ricorsivo. In secondo luogo, invece di passare i nuovi valori all'iterazione successiva del ciclo, li passa alla ricorsione successiva. Nel metodo iterativo, le iterazioni possono essere controllate attraverso le condizioni di loop, mentre nel metodo ricorsivo, il massimo e il minimo sono usati come condizioni al contorno.

Nel metodo iterativo, la complessità spaziale sarebbe O(1). Mentre nel metodo ricorsivo, la complessità spaziale sarebbe O(log n).

Benefici

• Un algoritmo di ricerca binaria è un algoritmo di ricerca abbastanza semplice da implementare.

• Si tratta di un miglioramento significativo rispetto alla ricerca lineare e ha prestazioni quasi identiche rispetto ad alcuni degli algoritmi di ricerca più difficili da implementare.

• L' algoritmo di ricerca binaria suddivide l'elenco a metà a ogni iterazione, anziché scorrere l'elenco in sequenza. Su elenchi di grandi dimensioni, questo metodo può essere davvero utile.

Checkout: Classificazione dell'albero decisionale: tutto ciò che devi sapere

Conclusione

Un algoritmo di ricerca binaria è un algoritmo ampiamente utilizzato nel dominio computazionale. È un algoritmo di ricerca grasso e accurato che può funzionare bene su set di dati grandi e piccoli. Un algoritmo di ricerca binaria è un algoritmo semplice e affidabile da implementare. Con l'analisi del tempo e dello spazio, i vantaggi dell'utilizzo di questa particolare tecnica sono evidenti.

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al Diploma PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1- on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.