我写了一个函数,它的输入是一个按照从小到大顺序排列的唯一整数列表。我应该在列表中找到与索引值相匹配的索引。例如,如果L[2]==2,则输出为true。
因此,在O(logn)的复杂度下完成了第一部分后,现在我想找出在给定列表中有多少个索引像这样行为的索引,其复杂度也为O(logn)。
我上传了我的第一个代码来完成第一部分,以及我需要帮助的第二个代码:
def steady_state(L):
lower= 0
upper= len(L) -1
while lower<=upper:
middle_i= (upper+ lower)//2
if L[middle_i]== middle_i:
return middle_i
elif L[middle_i]>middle_i:
upper= middle_i-1
else:
lower= middle_i +1
return None
def cnt_steady_states(L):
lower= 0
upper= len(L) -1
a=b=steady_state(L)
if steady_state(L)== None:
return 0
else:
cnt=1
while True:
if L[upper] == upper and a<=upper:
cnt+= upper-a
upper= a
if L[lower]== lower and b>=lower:
cnt+= b- lower
lower = b