Find smallest index that is identical to the value in an array
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