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

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

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