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