How to use recursion on divide and conquer to find A[i] = i
<p>I'm trying to use recursive binary search method in order to find when A[i] = i given a distinct number of 'n' elements sorted in ascending order.</p>

<p>I understand how to use the recursive binary search method given the target I need to search for, but I can't seem to implement when I have to increment key value by one and search for when A[i] = i.</p>

<pre><code>public static int match_dac( int[] A, int n )
{
    return dnq(A, 0, n-1, 0);
} 

public static int dnq(int[] A, int left, int right, int key) {
    if (left &lt; right) {
        int centre= (left + right) / 2;
         if (A[centre] &lt; centre) {
            return dnq(A, left, centre, key+1); 
        } else if (A[centre] &gt; centre) {
            return dnq(A, centre + 1, right, key + 1);
        } else {
            return centre;
        }


    }

    return -1;
}
</code></pre>

<p>This is what I have so far.</p>

<p>Any help would be appreciated, thanks!</p>

<p><strong>Edit:</strong></p>

<pre><code>public static int match_dac( int[] A, int n )
{
    return dnq(A, 0, n - 1);

} 

public static int dnq(int[] A, int left, int right) {
    if (left &lt; right) {
        int centre= (left + right) / 2;
        if (A[centre] &gt; centre) {
            return dnq(A, left, centre); 
        } else if (A[centre] &lt; centre) {
            return dnq(A, centre + 1, right);
        } else {
            return centre;
        }
    } else if (left == right) {
        if (left == A[right])
            return left;
    }
    return -1;
}
</code></pre>

<p>It works now, thank you for your help. I added in the last else if statement because my method didn't capture if the last element equaled to the corresponding index (ie. A[8] = 8 when size of array is 9, and no other hits exist other than last element). Other than that, flipping the signs and using the centre as the key worked perfectly. Thanks!</p>