Finding an index such that $A[i] = i$ in a strictly increasing integer array I'm looking for a hint for solving the following problem : 


  Given an array $A[1, \dots, k]$ of integers where $A[1] &lt; A[2] &lt; \dots &lt; A[k]$ 
  write pseudocode for an algorithm that determines whether $A[j]=j$ for some $j\in \{1,\dots,k\}$. Worst-case running time should be $\Theta(\log k)$.


I shall find an easy to calculate criteria which finds the index involving the special structure of $A$.

Let's say $A = [-3 , 2 , 4, 5, 7, 8, 9, 10]$. My first approach would be to subdivide $A$ into two parts around the median (here $A[4]$). Since $A[4] = 5 &gt; 4$ and the sequence keeps increasing, I don't have to look at $A[4,\dots,8]$.

My criterion would then be: For a sequence of numbers $A[a, \dots, b]$, if $A[a] &gt; a$, then the solution can't be in that sequence since $A[a]&lt; \dots &lt; A[b]$. 

Am I going in the right direction?
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.