Find smallest index that is identical to the value in an array The task is taken from LeetCode


  Given an array A of distinct integers sorted in ascending order,
  return the smallest index i that satisfies A[i] == i.  Return -1 if no
  such i exists.
  
  Example 1:

Input: [-10,-5,0,3,7]
Output: 3
Explanation: 
// For the given array, A[0] = -10, A[1] = -5, A[2] = 0, A[3] = 3, thus the output is 3.

  
  Example 2:

Input: [0,2,5,8,17]
Output: 0
Explanation: 
// A[0] = 0, thus the output is 0.

  
  Example 3:

Input: [-10,-5,3,4,7,9]
Output: -1
Explanation: 
// There is no such i that A[i] = i, thus the output is -1.

  
  Note:
  
  1 &lt;= A.length &lt; 10^4
  
  -10^9 &lt;= A[i] &lt;= 10^9


My solution

has time complexity of \$O(n)\$ and space complexity of \$O(1)\$. I start to look from the start to the last element. If I find a value that is greater than i, then I can exit early (because there won't be an element that is equal to i anymore). If I find A[i] === i, then I have a result.

Is there a faster solution than the one provided?

/**
 * @param {number[]} A
 * @return {number}
 */
var fixedPoint = function(A) {
    for (let i = 0; i &lt; A.length; i++) {
        if (A[i] &gt; i) { return -1; }
        if (A[i] === i) { return i; }
    }
    return -1;
};
Review

Your solution naively walks the array of ascending integers from starting position s = 0. In some situations, this means you are walking tons of negative numbers, knowing they can never match an array index, which is always nonnegative. 

Optimization

You could optimize s before walking the array. Since array indices are nonnegative integers, you should skip walking the array where the values are strict negative.

As en example, if input = [-10000, -9999, ..., 0, 1] you just want to check 0 and 1.

The way I would optimize the algorithm:


determine starting point s


if first item is positive: s = 0
if last item is strict negative: return -1
perform binary search to find s (you want s to hold the first positive integer in the array)

walk i as from s to end of array


on match: return match
on array[i] > i: return -1
on end reached without match: return -1



Optimized Time Complexity

~\$0(\lg m)\$ with m &lt;= n and m being the number of positive integers in the array