count all array[index] == index occurrences
Now let's see if I understand your problem: Given a sorted list of unique numbers you want to find all instances where list[i] == i (the important part is the unique).


This means each number in the list is at least 1 larger than the previous number.
Assume that list[k] == x &lt; k. Because the numbers are strictly increasing it must be that list[k-1] &lt;= x-1 &lt; k-1, list[k-2] &lt;= x-2 &lt; k-2, ... list[k-l] &lt;= x-l &lt; k-l. So if you have an index where the value is smaller than the index then this must also be the case for all previous indices.
Assume that list[k] == x &gt; k. Because the numbers are strictly increasing it must be that list[k+1] &gt;= x+1 &gt; k+1, list[k+2] &gt;= x+2 &gt; k+2, ... list[k+l] &gt;= x+l &gt; k+l. So if you have an index where the value is larger than the index then this must also be the case for all following indices.


The conclusion from these points is that a list with the given properties can be divided into three parts


Start 0 &lt;= s &lt; ms with list[s] &lt; s
Middle ms &lt;= m &lt; me with list[m] == m
End me &lt;= e &lt; n with list[e] &gt; e


Your problem is to find the middle part. The number of items where list[i] == i is then me - ms.

This can be solved by finding the largest index for which list[k] &lt; k and the smallest index for which list[k] &gt; k (or the smallest and largest indices for which list[k] == k - depends on how you want to write the search criteria).

Using two binary searches should yield the desired results which will guarantee a worst case complexity of O(log(n))

Update: Your original implementation is effectively a binary search which will find both end and start point of the middle sequence so you implementation is O(log(n))