We are given a sorted array$A[1..n]$, we are searching to find an element that $A[i]=i^2$ in array. How we can prove that we can't do it in $O(\log n)$?
My idea: do a linear search in array in $O(n)$, and check: if $A[i]=i^2$ print it. The teacher say it can't be done in $O(\log n)$,and i want to prove it can't be done in $O(\log n)$ time.