Made Easy Test Series:Algorithm

Question

Given a sorted array of distinct integer $A\left [ 1,2,....n \right ]$, the tightest upper bound to check the existence of any index $i$, for which $A[i]=i$ is equal to _______________

---

I thought here answer that mean time complexity will be $O(1),$ because directly getting the searching index and then checking if $A[i]=i$, but answer given as $O(log n).$Please help me out, which will be correct answer?

Comments

ma'am, how it can be O(1).

Suppose, there are 13 elements in  array A like :-

A[0] = -15

A[1] = -13

A[2] = -11

A[3] = -8

A[4] = -7

A[5]= -3
mid1= A[6]= -2

A[7] = 0
A[8] = 2

mid2=A[9] = 7

A[10]= 9

mid3 = A[11]= 11

A[12]= 55

Since, array is sorted. So, 1st think about binary search. suppose mid means middle. Now, consider cases like :-

1)  If A[mid] > mid then possibility of A[i] = i will be in the previous half from A[mid].
2) if A[mid] < mid then possibility of A[i] =i will be in next half from A[mid].
3) if A[mid] = mid then you don't have to do anything because your objective is already completed.
Now,  if you apply it in above example then first we check middle element i.e. A[mid1] = -- 2 and mid1 is 6.  so here,  - 2 < 6..so apply case 2..then you will go in next half.  Like this you can find A[i] =i if it exists.

---

@ankit here we need to check every element

right?

We donot know if any element is matching as A[i]=i

otherwise not matching

We have to check each and every element. So, then why not O(n) ??

---

yes mam. It can be O(n) but question is about tightest upper bound.

---

@ankitgupta.1729

thanks too good, got it :)

---

Sorry to say ankitgupta.1729 . But it can never be O(n). Because we are discarding one half of our search space at every instant , the recurrence is of the form T(n)=T(n/2)+c . The solution is O(logn).

---

@Arkaprava

it can be O(n) by checking each element with its index but one better algo will give O(lgn) which I mentioned above. 

---

In this the lower bound would be O(1) right ?

since first element could be the answer.

---

how can lower bound be of big-oh?

---

oh my mistake it should be $\Omega$(1) right ?

Answer 1

using binary search it will take O(logn)

mid=low+high/2

compare      (key > mid)

                 mid+1,high

                     (key<mid)

                low, mid-1