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

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