Given sorted integer array, write an algo based on divide and conquer for A[i]=i

The requirement that the input is sorted in itself is not enough. The additional requirement that there are no two equal values in the input array is a necessary condition to be able to use a binary search.

If that would not be a condition, you could not use a binary search, as can be seen in the following example (assuming 0 is the first index):

    i:   0 1 2 3 4 5 6
        --------------
  A[i]: -1 0 x 4 y 6 7
               ^

With a binary search you'd take the middle element and decide at which side of it there could be an i with A[i]=i. The problem is that in the above example the solution could be at either side of the centre: if x=2, then the solution is at the left, and when y=4, the solution is at the right. So divide and conquer will not work. Only when it is assured that the input has no duplicate values, a divide and conquer algorithm can work.

On top of that you can immediately exclude input arrays where the first value is greater than 0, because then there is no way to achieve A[i]=i without having duplicate values. Similarly, an input array where the last value is less than the last index, does not have an i with A[i]=i.

This consideration will also work during the divide and conquer. Take this example:

    i:   0 1 2 3 4 5 6 7 8
        -------------------
  A[i]: -4 0 1 2 5 6 7 8 10

At first both values at the ends are verified: they don't exclude a solution, so the middle value at index 4 is taken. Since its value (5) is greater than the index (4), the range from index 4 to 8 can be ignored. So in the next iteration of the algorithm the range between index 0 and 3 (included) are considered.

But the value at the rightmost index (3) is less than 3 (it is 2). By the above mentioned rule, this means there cannot be a solution, and so the algorithm can stop right there: making more divisions would be futile.

So here is a JavaScript implementation for this:

function hasSelfReference(arr) {
    let last = arr.length - 1;
    if (last < 0 || arr[0] > 0 || arr[last] < last) return false;

    let first = 0;
    while (first < last) {
        let mid = (first + last) >> 1;
        if (arr[mid] < mid) {
            first = mid + 1;
            if (arr[first] > first) return false;
        } else if (arr[mid] > mid) {
            last = mid - 1;
            if (arr[last] < last) return false;
        } else 
            return true;
    }
    return arr[first] === first; // arr[first] may be undefined: not a problem in JS
}

console.log(hasSelfReference([3, 4, 5, 6])); // false
console.log(hasSelfReference([-4, -2, 1, 2, 7])); // false
console.log(hasSelfReference([-4, -2, 1, 3, 7])); // true
console.log(hasSelfReference([])); // false
console.log(hasSelfReference([-4, 0, 1, 2, 5, 6, 7, 8, 10])); // false

As with the usual divide and conquer algorithms, this has a O(logn) (worst-case) time complexity.

When the array has a matching index, then the number of iterations is logn, but when there is no match, and the array is large, there will often be an early exit out of the loop.