I wrote a function that gets as an input a list of unique ints in order,(from small to big). Im supposed to find in the list an index that matches the value in the index. for example if L[2]==2 the output is true. so after i did that in complexity O(logn) i now want to find how many indexes behave like that in the given list with the same complexity O(logn). im uploading my first code that does the first part and the second code which i need help with:

def steady_state(L):lower= 0upper= len(L) -1while lower<=upper:middle_i= (upper+ lower)//2if L[middle_i]== middle_i:return middle_ielif L[middle_i]>middle_i:upper= middle_i-1else:lower= middle_i +1return Nonedef cnt_steady_states(L):lower= 0upper= len(L) -1a=b=steady_state(L)if steady_state(L)== None:return 0else:cnt=1while True:if L[upper] == upper and a<=upper:cnt+= upper-aupper= aif L[lower]== lower and b>=lower:cnt+= b- lowerlower = b

It's not possible with the restrictions you've given yet. The best complexity you can theoretically achieve is O(­n).

O() assumes the worst case (just a definition, you could drop that part). And in the worst case you will always have to look at each item in order to check it for being equal to its index.

The case changes if you have more restrictions (e. g. the numbers are all ints and none may appear more than once, i. e. no two consecutive numbers are equal). Maybe this is the case?

EDIT:

After hearing that in fact my assumed restrictions apply (i. e. only once-appearing ints) I now propose this approach: You can safely assume that you can have only exactly one continuous range where all your matching entries are located. I. e. you only need to find a lower bound and upper bound. The wanted result will then be the size of that range.

Each bound can safely be found using a binary search, of which each has O(log n).

def binsearch(field, lower=True, a=0, b=None):if b is None:b = len(field)while a + 1 < b:c = (a + b) / 2if lower:if field[c] < c:a = celse:b = celse:  # search for upper boundif field[c] > c:b = celse:a = creturn b if lower else adef indexMatchCount(field):upper = binsearch(field, lower=False)lower = binsearch(field, b=upper+1)return upper - lower + 1

This I used for testing:

field = list({ random.randint(-10, 30) for i in range(30) })
field.sort()
upper = binsearch(field, lower=False)
lower = binsearch(field, b=upper+1)
for i, f in enumerate(field):print lower <= i <= upper, i == f, i, f