How to use the step count method correctly for binary search?

Question

I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be O(n) and not O(log(n)).

My implementation:

fn binarySearch(array:[i32;20],target:i32) -> isize{
    let mut min = 0; //c
    let mut max = array.len(); //c
    let mut guess:usize; ///c
    while max > min{ //n
        guess = (max+min)/2; //c
        println!("Guess: {}",array[guess]);//c
        if array[guess] == target{//c
            return guess as isize;
        }else if array[guess]<target{//c
            min = guess + 1; //c
        }else{//c
            max = guess - 1; //c
        }
    }
    return -1 as isize; //c
} 

I've written the time it takes in the comments c for constant n for linear. But based on this I get something like this: T(n) = c+c+c+n*(c+c+c+c+c+c+c+c) which should boil down to T(n) = 3c+n*8c which would be O(n) and not O(log(n)).

Answer 1

The mistake in your analysis is counting the number of iteration of the while loop as $n$. The key observation with binary search is that you cut the range at about half in every iteration. So if initially your array has $n$ items, in the worst-case you will divide the array in half $k$ times until only one element is left (after this the subarray will be empty and the loop will end). You will get $n/2^k = 1$, which then is equal to $n=2^k$. Here $k$ is also the worst-case number of iterations. Taking the logarithm both sides will give you $k =\log_2 n$.

Answer 2

Hint:

On the first iteration, guess = n/2 and either the search ends there or continues in [0, n/2-1] or [n/2+1, n].

On the second iteration, guess = n/4-1/2 or 3n/4+1/2, and either the search stops there or continues in [0, n/4-3/2] or [n/3+1/2, n] or [n/2+1, 3n/4-1/2] or [3n/4+3/2, n].

And so on. The details of the bounds do not matter so much. What matters is that the interval size is halved every time.