FInd the minimum number of times the search loop will execute an array of of 1,048,57

Hello Everyone,

I want to know if any body can help me find the minimum number of times the search loop will execute this array if the search algorithm is an binary search
and sequential search?

I think I have it right for the maximum number of times of either algorithm:

Here is my work out solutions:

binary search? Maximum: log2(1,048,576)= 20 times
sequential search? Maximum: 1,048,576 + 1 ÷ 2= 524,289 times

Reply 1

seanbruce

14

id say 3
my method is 2+1=3

Reply 2

Mik9

OP

3

Original post by seanbruce

id say 3
my method is 2+1=3

@seanbruce Care to show more work and explain yourself further for how you arrived at the solution for either algorithm?

(edited 6 years ago)

Reply 3

melwilliams3000

9

Original post by Mik9

Hello Everyone,

I want to know if any body can help me find the minimum number of times the search loop will execute this array if the search algorithm is an binary search
and sequential search?

I think I have it right for the maximum number of times of either algorithm:

Here is my work out solutions:

binary search? Maximum: log2(1,048,576)= 20 times
sequential search? Maximum: 1,048,576 + 1 ÷ 2= 524,289 times

You've calculated the average number of searches for the sequential search, the maximum is actually is the size of the array - ie if the element is right at the end.

The minimum for each search is 1.

For binary search say your element was in the middle the sorted array then only one loop would be required and the function would exit having found the number straight away.
For sequential if your element is the first then that would result in 1 loop being run

FInd the minimum number of times the search loop will execute an array of of 1,048,57

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you