count all array[index] == index occurrences

The method foo gets a sorted list with different numbers as a parameter and returns the count of all the occurrences such that: i == list[i] (where i is the index 0 <= i <= len(list)).

def foo_helper(lst, start, end):

    if start > end:
        # end of recursion
        return 0

    if lst[end]  start:
        # no point checking this part of the list
        return 0

    # all indexes must be equal to their values
    if abs(end - start) == lst[end] - lst[start]:
        return end - start + 1

    middle = (end + start) // 2

    print(lst[start:end+1], start, middle, end)

    if lst[middle] == middle:
        #print("lst[" , middle , "]=", lst[middle])
        return 1 + foo_helper(lst, middle+1, end) + \
    foo_helper(lst, start, middle-1)

    elif lst[middle] < middle:
        return foo_helper(lst, middle+1, end)
    else:
        return foo_helper(lst, start, middle-1)

def foo(lst):
    return foo_helper(lst, 0, len(lst)-1)

My question is: is this code's worst-case complexity log(n)? If not, what should I do differently?

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

-
Assume that list[k] == x > k. Because the numbers are strictly increasing it must be that list[k+1] >= x+1 > k+1, list[k+2] >= x+2 > k+2, ... list[k+l] >= x+l > 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

• Middle ms






• End me 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] 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))`

StackExchange Code Review Q#35760, answer score: 4