0
$\begingroup$

I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can calculate the number of minimum times it will search through the array using both the binary search and sequential search. Here is what I have done so far.

Maximum Number of Times with Binary Search: Maximum: $\log_2(1,048,576)= 20$ times Maximum Number of Times with Sequential Search: Maximum: $1,048,576 + 1 ÷ 2= 524,289$ times

But I am confused about how I can obtained a solution with Minimum number for each algorithm. Any suggestions?

$\endgroup$
1
$\begingroup$

I assume your input is random and your array of size $N$, $A[1..N]$.

In case of binary search if the number you are searching for is located at $(1+N)/2$, i.e. right in the middle of the input array then you will find it after the first if-statement.

Similarly in case of sequential search, if number your are searching for is the first element of the array then you stop after the first if-statement.

In both cases you do only one comparison.

$\endgroup$

Your Answer

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

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