Complessità del tempo di ricerca binaria

La ricerca binaria è un paradigma di divisione. Cerca un elemento in un array ordinato. In questo articolo, viene considerato solo l'ordinamento ascendente. L'elemento da cercare è chiamato valore target. Il valore target può o non può essere trovato nell'array.

La ricerca inizia confrontando il valore target con l'elemento centrale dell'array ordinato. Se il numero di elementi nell'array è uniforme, allora l'articolo a metà del numero è considerato l'elemento centrale. Se il valore target è lo stesso dell'elemento medio, è stato trovato l'indice del valore target. Se non sono uguali, il valore target è più grande o più piccolo dell'articolo medio. Se è più grande, la metà inferiore dell'array verrà abbandonata affinché la ricerca continui nella metà superiore. Se è più piccolo, la metà superiore dell'array verrà abbandonata, affinché la ricerca continui nella metà inferiore.

La ricerca continua dividendo di nuovo la metà scelta in due. Viene effettuato un confronto tra il valore target e l'elemento medio di questa nuova metà. Se non sono gli stessi, allora questa metà è nuovamente divisa in due e per le stesse ragioni la metà precedente è stata divisa. Se il valore target non è uguale al nuovo elemento medio, la divisione continua.

Quando il valore target e un valore mediano (articolo) sono uguali, che sta conquistando. Lì e poi, la ricerca si ferma. Se il valore target non è nell'array, la ricerca si fermerà ad un elemento medio finale, che non è uguale al valore target.

Questo articolo mira a dare un apprezzamento chiamato complessità del tempo per la velocità della ricerca binaria.

Contenuto dell'articolo

• Introduzione - Vedi sopra
• Illustrazione di ricerca binaria
• Complessità temporale e ricerca binaria
• Coding in c
• Conclusione

Illustrazione di ricerca binaria

Considera l'elenco ordinato:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Dove l'intero, 3, deve essere perquisito. Naturalmente, la ricerca dall'inizio richiederà tre operazioni. Tuttavia, l'utilizzo della ricerca binaria richiederà quattro operazioni principali come segue:

Il valore target è 3. Dividi l'elenco in due rende 8 l'elemento centrale.

È 8 uguale a 3?

NO. Poiché 3 è inferiore a 8, la ricerca si concentrerà sulla metà inferiore. Questa è un'operazione principale eseguita.

Dividi di nuovo in due ne fa di nuovo 4 il nuovo oggetto medio.

È 4 uguale a 3?

NO. Poiché 3 è inferiore a 4, la ricerca si concentrerà sulla nuova metà inferiore. Questa è la seconda operazione principale eseguita.

Dividi di nuovo in due fa di nuovo 2 il nuovo oggetto medio.

È 2 uguale a 3?

NO. Poiché 3 è maggiore di 2, la ricerca si concentrerà quindi sulla nuova metà superiore. Questa è la terza operazione principale eseguita.

Dividi di nuovo in due fa di nuovo 3 il nuovo oggetto medio, di metà (sotto-list) di lunghezza, uno. Il nuovo e ultimo articolo di mezzo è ora 3.

È 3 uguale a 3?

SÌ. Il valore target è stato trovato. Questa è la quarta e ultima operazione principale eseguita.

Quando ci sono 16 articoli, è possibile eseguire un massimo di 4 operazioni principali. Se ci fossero 16 articoli e il valore target era nell'intervallo e non poteva essere trovato, 4 operazioni principali avrebbero comunque avuto luogo. Ad esempio, nell'elenco seguente:

1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

Ci sono ancora 16 articoli. Un valore target di 3 sarebbe terminato al valore di 5, con ancora 4 operazioni principali.

Complessità temporale e ricerca binaria

Prestazioni peggiori

Le prestazioni del caso peggiore si riferiscono al caso in cui il valore target si trova nell'ultima operazione principale, oppure il valore target è nell'intervallo di valori e non si trova nell'ultima operazione principale.

Quando il numero di elementi è 16, il numero massimo di operazioni sarà sempre 4.

16 = 2⁴
4 = log₂(16)

Sia N 16. COSÌ,

4 = log₂(N)

Se n è 8, il numero massimo di operazioni sarebbe 3 = log₂(8). Se n è 32, il numero massimo di operazioni sarebbe 5 = log₂(32).

Si dice che la complessità del tempo peggiore (velocità relativa) per la ricerca binaria sia:

O (log₂(N))

Dove la grande O e le sue parentesi hanno un registro₂(n) è la notazione per la complessità del tempo. È semplicemente scritto come:

O (log n)

Prestazioni migliori

Supponiamo che il valore target fosse 8 per il primo elenco sopra. In questo caso, la prima operazione principale avrebbe trovato la posizione del valore target. Questa è la prestazione migliore. La complessità temporale per questa prestazione migliore è stata scritta come:

O (1)

Dove 1 significa un'operazione principale.

Coding in c

Una funzione di ricerca binaria del codice C è:

#includere
int binarySearch (int arr [], int target, int n)
int loindex = 0;
int upindex = n - 1;
// Assicurati di avere ancora elementi nell'elenco da cercare
while (loindex target)
upindex = MiddleIndx;
altro
loindex = MiddleIndx + 1;


// restituisce un numero negativo quando non possiamo trovare il bersaglio nell'array
restituzione -1;

Il loindex indica l'indice più basso di metà (sotto-list). L'UPINDEX indica l'indice più alto di metà (sotto-list). All'inizio, loindex è 0 e Upindex è 15 quando n è 16. La condizione a circostazione di while garantisce che la divisione continui fino a quando loindex è uguale a Upindex se il valore target non è stato ancora trovato.

Una funzione principale C idonea per questo codice è:

int main (int argc, char ** argv)

int n = 16;
int target = 3;
int arr [] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
int indexFound = binarySearch (arr, target, n);
printf ("%d \ n", indicefound);
restituzione 0;

Conclusione

Questo articolo ha discusso della complessità del tempo di ricerca binaria e ha sottolineato le seguenti:

La complessità del tempo peggiore per la ricerca binaria è:
O (log n)

La complessità del tempo migliore per la ricerca binaria è:
O (1)