Finding an index such that $A[i] = i$ in a strictly increasing integer array
Let $B[i] = A[i] - i$. Since $A[i] &lt; A[i+1]$, we have $A[i]+1 \leq A[i+1]$ and so (subtracting $i+1$ from both sides) $B[i] \leq B[i+1]$. In other words, $B[1] \leq \cdots \leq B[k]$ is nondecreasing. Your goal is to find an index $i$ such that $B[i] = 0$, if any such exists. You can use binary search to do this in time $O(\log k)$. In fact, you can even find all such indices (or rather, a succinct representation of them) in that running time.