Given a sorted array of distinct integer $A[1,2.....n]$ 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?
If the array had $A[i]=i, \forall{i}$, then the complexity would have been $\theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.
But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.
The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.
The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $\theta(log_2n)$
Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?
(If you figure that out, the solution is trivial).
The best searching method for this problem will be binary search and in binary search time complexity of avg or worst case is logn.
and if in question it is not mentioned distict intergers then we can't apply binary search then it we go with linear so in that case time complexity will be o(n).
