sorted array, how many comparisions to find if element in

Question

I have a sorted array, and a number, how many maximum comparisons should I do to find if the number is contained in the array ?

Suppose we have a million of numbers in the array.

to add to the previous comment, you can't say you will do log(1 million) comparisons because time complexity is rough and there is a constant to multiply with (that can be as small as 1 or less or as big as 1000 or more) — Ayoub Omari, Sep 17 '20 at 13:46
Hint: get the median value array[N/2] and check if it is equal, larger or smaller than the target — Damien, Sep 17 '20 at 13:48
@Damien, I uderstand that, but how calculate how many max comparisions should I do however — serge, Sep 17 '20 at 13:49
The size of the array you examine = n, n/2, n/4, ...n/(2^steps). The maximum number of steps is such that n/(2^nsteps) = 1, i.e. nsteps = log2(n) — Damien, Sep 17 '20 at 13:55
Does this answer your question? [Find element in a sorted array](https://stackoverflow.com/questions/40810090/find-element-in-a-sorted-array) — Turing85, Sep 25 '20 at 16:36

score 1 · Accepted Answer · answered Sep 17 '20 at 15:26

1

To complete the answer from @aponeme, the maximum number of comparisons is equal to

2*upper(log2(n))

The reason is that the size of the array you examine is equal to

n, n/2, n/4, ...n/(2^steps).

Then the maximum number of steps is such that

 n/(2^nsteps) = 1, i.e. nsteps = log2(n)

answered Sep 17 '20 at 15:26

Damien

finally, for the concrete scenario with a n = million, the maximum number of comparisions would be log2(1000000) = 20 – serge Oct 08 '20 at 22:02

apomene · Answer 2 · 2020-09-17T13:50:43.137

0

With divide and Conquer or Binary search (pseudo - code):

Split the array in half
If number is bigger than max of first half work with the second half else work with first half
Repeat step 1 - 2 with the remaining half

Worst case scenario: Need to divide into two arrays each of length 1 => O(logN)

edited Sep 17 '20 at 13:50

answered Sep 17 '20 at 13:49

apomene

I understand the algorithm, but the question is how much max comparisions should I perform – serge Sep 17 '20 at 13:49
You need to add the base case when you find the element, and the worst case when the elements don't appear in the list – Ayoub Omari Sep 17 '20 at 13:50
sorry, I am not expert in this. I have one million items 2, 4, ... 1 999 998, 2 000 000, i need to check if the element 1000 001 is in the list. How much comparations should I do, and why? – serge Sep 17 '20 at 13:55
@Siege refer to Damien last comment, I think it suffies – apomene Sep 17 '20 at 13:57
@apomene, please mention that answer in yours, in order I be able to mark it as answered – serge Sep 17 '20 at 13:59
@Serge your question is a little bit confusing. There is no such a thing you "should do". It's up to you, prior to the algorithm design, to fix your time complexity requirements. Also we only talk about Big-O notation to estimate the performance of the algorithm, there is no fixed number – Ayoub Omari Sep 17 '20 at 14:00
@quade: is 20 the answer, how is not a fixed number? – serge Sep 17 '20 at 14:26

2 Answers2