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.
argument , if
), the mark never gets wrapped to a line different from what it terminates.)I tried to design an adversarial argument but it didn't seem to go in the correct direction.
Show what you tried! $\endgroup$