Complessità temporale Di Ricerca binaria È O(log n) , Dove N è il numero di elementi nell'array. Divide l'array a metà ad ogni passaggio. Complessità spaziale È O(1) poiché utilizza una quantità costante di spazio extra.

esempi di alberi binari

Esempio di algoritmo di ricerca binaria

Le complessità temporali e spaziali dell'algoritmo di ricerca binaria sono menzionate di seguito.

Complessità temporale di Algoritmo di ricerca binaria :

Migliore complessità temporale dell'algoritmo di ricerca binaria: O(1)

Il caso migliore è quando l'elemento si trova nell'indice centrale dell'array. È necessario un solo confronto per trovare l'elemento di destinazione. Quindi la complessità del caso migliore è O(1) .

Complessità media del tempo di caso dell'algoritmo di ricerca binaria: O(logN)

Considera l'array arr[] di lunghezza N ed elemento X essere trovato. I casi possono essere due:

ssh in formato completo

• Caso 1: L'elemento è presente nell'array
• Caso2: L'elemento non è presente nell'array.

Ci sono N Caso 1 e 1 Caso2. Quindi numero totale di casi = N+1 . Ora nota quanto segue:

• Un elemento con indice N/2 può essere trovato in 1 confronto
• Gli elementi con indice N/4 e 3N/4 si trovano in 2 confronti.
• Gli elementi agli indici N/8, 3N/8, 5N/8 e 7N/8 si trovano in 3 confronti e così via.

Sulla base di ciò possiamo concludere che elementi che richiedono:

• 1 confronto = 1
• 2 confronti = 2
• 3 confronti = 4
• X confronti = 2 ^x-1 Dove X appartiene alla gamma [1, logN] perché confronti massimi = tempo massimo N può essere dimezzato = confronti massimi per raggiungere il 1° elemento = logN.

Quindi, confronti totali
= 1*(elementi che richiedono 1 confronto) + 2*(elementi che richiedono 2 confronti) + . . . + logN*(elementi che richiedono confronti logN)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^calma* (logN – 1) + 1
= N * (logN – 1) + 1

Numero totale di casi = N+1 .

Pertanto, la complessità media = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Qui il termine dominante è N*logN/(N+1) che è approssimativamente calma . Quindi la complessità media del caso è O(logN)

Peggiore complessità temporale dell'algoritmo di ricerca binaria: O(logN)

Il caso peggiore sarà quando l'elemento è presente nella prima posizione. Come visto nel caso medio, il confronto richiesto per raggiungere il primo elemento è calma . Quindi la complessità temporale nel caso peggiore è O(logN) .

Complessità spaziale ausiliaria dell'algoritmo di ricerca binaria

IL complessità dello spazio ausiliario del Algoritmo di ricerca binaria È O(1) , il che significa che richiede una quantità costante di spazio aggiuntivo indipendentemente dalla dimensione dell'array di input. Questo perché la ricerca binaria è un algoritmo iterativo che non richiede strutture dati aggiuntive o ricorsione che cresce con la dimensione dell'input. Tuttavia, possiamo anche implementare la ricerca binaria in modo ricorsivo.

converte la stringa in intero