Lower-bound of a decision problem What's the lower-bound of the decision problem that decides:

Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = {0,1,1,3,4,4,5}.)

Is there any sub-linear deterministic algorithm can solve the problem?
There is no sub-linear algorithm for it, assuming the array may have duplicates as in your example. The following shows that any algorithm must read all of $|A|$'s values.

Assume that there's sub linear algorithm $Alg$ that decides it.

Define an array $A$ by $A_k = k+1$.

Since $alg$ is sublinear, there has to be some cell of $A$ he didn't query. Denote such cell's index by $i$.

Define $B_k = \left\{
 \begin{array}{ll}
  k+1  &amp; \mbox{if } k \neq i \\
  i &amp; \mbox{if } k = i \\
 \end{array}
\right.$

Note since $Alg$ doesn't read cell $i$, it will answer the same for both $A$ and $B$, but obviously one of these answers is wrong..