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] < end or lst[start] > 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?
count all array[index] == index occurrences
python;array;recursion;binary search;complexity
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 < 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 smaller than the index then this must also be the case for all previous indices.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 partsStart 0 <= s < ms with list[s] < sMiddle ms <= m < me with list[m] == mEnd me <= e < n with list[e] > eYour 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 and the smallest 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))