# 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 < A < \dots < 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$). Since $A = 5 > 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] > a$, then the solution can't be in that sequence since $A[a]< \dots < A[b]$.

Am I going in the right direction?

• Can you edit your question to credit the original source for the problem? – D.W. Jan 8 '18 at 18:54
• The way to tell whether you are going in the right direction is to keep going, try to write out a specific algorithm (e.g., write pseudocode), test it on some examples, and then prove it correct. Have you tried doing that? How much progress have you made? Where specifically did you get stuck? If you haven't tried it yet, it'd be better to spend some time trying that and getting as far as you can on your own before asking here, and then if you get stuck at some point, ask a specific question about that aspect you're stuck on. – D.W. Jan 8 '18 at 18:56
• It's a task from my course algorithms & data structures at university. – moepmoep12 Jan 8 '18 at 18:58
• Actually I was stuck on finding any criteria. While writing it I found the one above. Writing out the problem often helps to solve it. – moepmoep12 Jan 8 '18 at 19:01

Let $B[i] = A[i] - i$. Since $A[i] < 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 \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.

My solution would be :

int Search( A , start = 1,end = A.length)
m = (start + end + 1) / 2 ( rounded down )  // calculates median

if ( end - start >= 0 )

if ( A[m] == m )                       // checks if solution found
return m

if ( A[m] > m )
return Search( A, start , m-1)   // solution must be in left subarray

else
return Search(A, m+1, end)      // solution must be in right subarray
else
return -1;                           // no solution exists

• This is not a coding site. Please explain your algorithm in words, additionally explaining why it works and why its running time is as required. – Yuval Filmus Apr 8 '18 at 21:42