Tidskomplexitet av Binär sökning är O(log n) , var n är antalet element i arrayen. Den delar upp arrayen på mitten vid varje steg. Rymdkomplexitet är O(1) eftersom det använder en konstant mängd extra utrymme.

ms word snabbåtkomstverktygsfält

Exempel på binär sökalgoritm

Tids- och rymdkomplexiteten för den binära sökalgoritmen nämns nedan.

Tidskomplexiteten av Binär sökalgoritm :

Bästa fall av tidskomplexitet för binär sökalgoritm: O(1)

Bästa fallet är när elementet är i mittindexet av arrayen. Det krävs bara en jämförelse för att hitta målelementet. Så det bästa fallets komplexitet är O(1) .

Genomsnittlig falltidskomplexitet för binär sökalgoritm: O(log N)

Överväg array arr[] av längd N och element X att bli hittad. Det kan finnas två fall:

• Fall 1: Element finns i arrayen
• Fall 2: Elementet finns inte i arrayen.

Det finns N Fall1 och 1 Fall2. Så totalt antal fall = N+1 . Lägg nu märke till följande:

• Ett element vid index N/2 kan hittas i 1 jämförelse
• Element vid index N/4 och 3N/4 finns i 2 jämförelser.
• Element vid index N/8, 3N/8, 5N/8 och 7N/8 finns i 3 jämförelser och så vidare.

Baserat på detta kan vi dra slutsatsen att element som kräver:

datastruktur

• 1 jämförelse = 1
• 2 jämförelser = 2
• 3 jämförelser = 4
• x jämförelser = 2 ^x-1 var x tillhör sortimentet [1, logN] eftersom maximala jämförelser = maximal tid N kan halveras = maximala jämförelser för att nå 1:a elementet = logN.

Alltså totala jämförelser
= 1*(element som kräver 1 jämförelser) + 2*(element som kräver 2 jämförelser) + . . . + logN*(element som kräver logN-jämförelser)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^lugna* (logN – 1) + 1
= N * (logN – 1) + 1

Totalt antal fall = N+1 .

Därför är den genomsnittliga komplexiteten = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Här är den dominerande termen N*logN/(N+1) vilket är ungefär lugna . Så den genomsnittliga ärendekomplexiteten är O(logN)

print array i java

Värsta fallets tidskomplexitet för binär sökalgoritm: O(log N)

Det värsta fallet kommer att vara när elementet är närvarande i den första positionen. Som ses i det genomsnittliga fallet är den jämförelse som krävs för att nå det första elementet lugna . Så tidskomplexiteten för värsta fall är O(logN) .

Auxiliary Space Complexity of Binary Search Algorithm

De extra rymdkomplexitet av Binär sökalgoritm är O(1) , vilket innebär att det kräver en konstant mängd extra utrymme oavsett storleken på inmatningsmatrisen. Detta beror på att binär sökning är en iterativ algoritm som inte kräver några ytterligare datastrukturer eller rekursion som växer med indatastorleken. Även om vi också kan implementera binär sökning rekursivt.