How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers

Question

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?

Answer 1

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.