I have doubt about recurrence relation for number of comparisons in binary search.
I read that recurrence can be written as T(n) = T(n/2) + 1 in this website http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L14-RecRel.htm
According to me it should be T(n) = T(n/2) + 2, as in worst case the element might not be present in the array and we end up doing 2 comparisons in each pass.
Please tell me whether I am right or wrong.
I think you are right.
IMHO, compare a b means we know a=b, a>b or a<b at the same time. That is to say, 1 comparison may have 3 different results.
But for programming languages. We have to use 2 comparisons.
if mid == x: found it! # 1st
else if mid < x: search right # 2nd
else: search left
You mean the == and < are 2 comparisons.
It does not affect the result though. Because we use big O notation to represent the complexity. It is just a matter of constant, but O usually don't care about it.
According to master theorem. Either +1 or +2 will result the same complexity O(log n).
What we want is usually a limit (Big-O), not a mathematical equation precise result.
I think what matters here is that 1 and 2 are both constant time. We can also split ==, > into machine instructions, and it may be greater than 2. Or maybe some programming languages or CPU utilize the comparison, it only cost 1 comparison. But it does not matter here when doing asymptotic analysis.