0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you tried actually running the algorithm for $n=1$, $n=2$, $n=3$, etc? Please show what you have got. $\endgroup$ – John L. Feb 2 at 14:01
  • 1
    $\begingroup$ yeah i think i figured out why it might be log(n) + 1. if n = 1 with my solution you get log(0) lol... $\endgroup$ – Iamlearningmath Feb 2 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.