I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing something.
function binary_search_alternative(Array, k) is L := 0 R := n − 1 while L < R do m := floor((L + R) / 2) if k > A[m] then L := m + 1 else: R := m if A[L] == k then return L return unsuccessful
My thinking is that at each iteration we are taking an array (n-1) and after each iteration we are halving it so floor((n-1)2^i), where floor((n-1)2^i) = 1, this is before the last iteration, and my calculations show that the number of comparisons for this one is log(n-1), but the article said that it was log(n) + 1. Wikipedia has a similar code, and they say the same thing. How is that?