Tijdcomplexiteit van Binaire zoekopdracht is O(logboek n) , waar N is het aantal elementen in de array. Het verdeelt de array bij elke stap in tweeën. Complexiteit van de ruimte is O(1) omdat het een constante hoeveelheid extra ruimte gebruikt.

overwinteren dialect

Voorbeeld van een binair zoekalgoritme

De tijd- en ruimtecomplexiteit van het binaire zoekalgoritme wordt hieronder vermeld.

Tijdcomplexiteit van Binair zoekalgoritme :

Best Case Tijdcomplexiteit van binair zoekalgoritme: O(1)

Het beste geval is wanneer het element zich in de middelste index van de array bevindt. Er is slechts één vergelijking nodig om het doelelement te vinden. Dus de beste case-complexiteit is O(1) .

Gemiddelde case-tijdcomplexiteit van binair zoekalgoritme: O(log N)

Overweeg array arr[] van lengte N en element X gevonden worden. Er kunnen twee gevallen zijn:

• Zaak 1: Element is aanwezig in de array
• Geval2: Element is niet aanwezig in de array.

Er zijn N Geval1 en 1 Geval2. Dus totaal aantal gevallen = N+1 . Let nu op het volgende:

• Een element met index N/2 is te vinden in 1 vergelijking
• Elementen met index N/4 en 3N/4 zijn te vinden in 2 vergelijkingen.
• Elementen met indices N/8, 3N/8, 5N/8 en 7N/8 zijn te vinden in 3 vergelijkingen enzovoort.

Op basis hiervan kunnen we concluderen dat elementen die vereisen:

pvr volledige vorm

• 1 vergelijking = 1
• 2 vergelijkingen = 2
• 3 vergelijkingen = 4
• X vergelijkingen = 2 ^x-1 waar X behoort tot het assortiment [1, logN] omdat maximale vergelijkingen = maximale tijd N kan worden gehalveerd = maximale vergelijkingen om het eerste element te bereiken = logN.

Totale vergelijkingen dus
= 1*(elementen waarvoor 1 vergelijking nodig is) + 2*(elementen waarvoor 2 vergelijkingen nodig zijn) + . . . + logN*(elementen waarvoor logN-vergelijkingen nodig zijn)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^kalm* (logN – 1) + 1
= N * (logN – 1) + 1

Totaal aantal gevallen = N+1 .

Daarom is de gemiddelde complexiteit = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Hier is de dominante term N*logN/(N+1), wat bij benadering is kalm . De gemiddelde complexiteit van een zaak is dus O(logN)

aws roodverschuiving

Worst Case Tijdcomplexiteit van binair zoekalgoritme: O(log N)

Het ergste geval zal zijn wanneer het element aanwezig is in de eerste positie. Zoals we in het gemiddelde geval kunnen zien, is de vergelijking die nodig is om het eerste element te bereiken gelijk kalm . Dus de tijdscomplexiteit voor het slechtste geval is O(logN) .

Hulpruimtecomplexiteit van binair zoekalgoritme

De complexiteit van de hulpruimte van de Binair zoekalgoritme is O(1) , wat betekent dat er een constante hoeveelheid extra ruimte nodig is, ongeacht de grootte van de invoerarray. Dit komt omdat Binary Search een iteratief algoritme is dat geen extra datastructuren of recursie vereist die meegroeit met de invoergrootte. Hoewel we Binary Search ook recursief kunnen implementeren.