CODEWITHSUNDEEP
algorithm
Tom
Tom

Reputation: 441

Binary Search number of comparisons

I wrote this recursive piece of code for standard binary search algorithm. I was just wondering when do I add +1 to the comparison counter ? pseud code below

Inputs A: Array of Data;
key:Data; L,R:Integer;
Variables m:Integer;
Returns m:Integer;

Begin
If R<L then return -1; fi
m:= (R+L)/2
if key = A[m] then return m; fi
if key > A[m] then
return binSearch(A,key,m+1,R);
Else
return binSearch(A,key,L,m-1);
fi
End

Does checking the L and R in the first if statement counts as comparison ? bit confused.

Upvotes: 0

Views: 313

Answers (2)

fersarr
fersarr

Reputation: 3529

I believe that when you say comparisons you dont mean strictly how many ifs you have, instead you are trying to get to the O(log(n)) complexity for binary search? if that is the case, why not count at the beginning of the function so you count the amount of calls made

Upvotes: 3

user1732445
user1732445

Reputation: 235

In asymtotic analysis, conditional statement considered as O(1).

Because conditional problem is decision problem. 0 or 1.

Upvotes: 0

Related Questions