Best Algorithm for searching for an index in an array such that A[i] = i

Question

Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log n)$ order of comparisons. The other part of question demanded to prove there exists no other algorithm which does better than this. I tried to design an adversarial argument but it didn't seem to go in the correct direction. How can one go about proving this with an adversary argument , if one exists. Other approaches to proving this are also welcome. My algorithm works as follows :

Search(A , start , end)
  Find mid
  if A[mid] > mid // the element with A[i] = i cannot exist in A [mid ... end]
    Search (A,start, mid-1)
  else if A[mid] < mid // the element with A[i] = i cannot exist in A [start... mid]
    Search(A,mid+1,end)
  else if(A[mid] = mid)
    return A[mid];
  else 
    return false;
end

Edit: edit contains my algorithm. Kindly forgive any typesetting errors

Answer 1

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index.

Edit: To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will work in no less than $O(\log(n))$. The proof involves information theorethic reasoning, since storing $n$ different numbers (the indices of the array) requires each to be represented by no less than $\log(n)$ bits. Now we can see, that in order for you to output/write the solution you need $\Omega(\log(n))$ bits, and you cannot do away with less (we can apply the same reasoning to comparisons since we need to compare $\log(n)$ bits to deduce whether one number is less than the other if they are the same on all but the last bit) This means that any algorithm will need atleast $O(\log(n))$ operations to produce output.

Now, obviously, since you have produced an algorithm working in $O(\log(n))$ then the bound is sharp.

to answer your question in the comment to this answer:

this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays?

while this is true for both unsorted and sorted arrays, it merely specifies a lower bound on the complexity of algorithms. This means that no algorithm can do better than $O(\log(n))$. It does not guarantee that there exists one though.

In an unordered array there are extra complexities that arrise, which prevent an $O(\log(n))$ solution. So we might say that the $\Omega(\log(n))$ is not sharp in this case since there does not exist an $O(\log(n))$ algorithm which could solve this problem for an unsorted array.

If we were to find a sharp lower bound for the unsorted array problem then we would need to use different assumptions and conduct a different analysis.

An important thing to realise is that this is all dependent on the underlying model of computations used. Is it assumed that comparisons take $O(1)$? How about writing a number to memory? If this is not defined then estimating complexity is tricky to say the least.