1
$\begingroup$

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)).

$\endgroup$

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.