解决O（logn）中的代码的难题
我写了一个函数，按照顺序（从小到大）将唯一整数列表作为输入。 我应该在列表中找到与索引中的值匹配的索引。 例如，如果L [2] = 2，则输出为真。 所以在我做了复杂的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
这是不可能的，你已经给出了限制。 理论上可以达到的最佳复杂度是O（n）。
O（）假定最坏的情况（只是一个定义，你可以放弃那部分）。 在最糟糕的情况下，您将不得不查看每个项目以检查它是否与索引相同。
如果您有更多的限制（例如，数字都是整数，并且没有一个可能出现多次，即没有两个连续数字相等），则案例发生变化。 也许情况是这样吗？
编辑：
在听说实际上我假设的限制适用（即只有一次出现的整数）后，我现在提出这种方法：您可以安全地假设您只能有一个连续范围，其中所有匹配条目都位于该连续范围内。 I. e。 你只需要找到一个下限和上限。 想要的结果将是该范围的大小。
每个绑定可以安全地使用二进制搜索找到，其中每个都有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) / 2
if lower:
if field[c] < c:
a = c
else:
b = c
else: # search for upper bound
if field[c] > c:
b = c
else:
a = c
return b if lower else a
def indexMatchCount(field):
upper = binsearch(field, lower=False)
lower = binsearch(field, b=upper+1)
return upper - lower + 1
我用于测试：
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
假设负整数是好的：
我认为关键在于，如果你的价值低于你的指数，你知道左边的所有指数也不符合它们的价值（因为整数是严格增加的）。 另外，一旦你得到一个索引的值大于索引，右边的所有内容都是不正确的（同样的原因）。 然后你可以像第一种情况那样做一个分而治之的算法。 沿着以下方向的东西：
check middle index:
if equal:
count = count + 1
check both halves, minus this index
elif value > index:
check left side (lower to index)
elif index > value:
check right side (index to upper)
在最坏的情况下（每个索引都匹配该值），我们仍然需要检查每个索引。
如果整数是非负数，那么你甚至更多。 您现在还知道，如果索引与该值匹配，则左侧的所有索引也必须与该值匹配（为什么？）。 因此，你会得到：
check middle index:
if equal:
count = count + indices to the left (index-lower)
check the right side (index to upper)
elif value > index:
check left side (lower to index)
elif index > value:
##Can't happen in this case
现在我们最糟糕的情况已经有了很大改善 我们不是找到一个匹配的索引，也没有从中获得任何新的信息，但是当我们找到一个匹配的时候，我们获得了大量的信息，现在知道一半的索引匹配。
如果“所有数字都是整数并且它们只出现一次”，那么你可以简单地对第一对数字进行二进制搜索，其中L[i]==i && L[i+1]!=i+1 。
要允许负整数，请检查L[0]<0 ，如果是，则在1..N之间搜索：
i>0 && L[i]==i && L[i-1]!=i-1 。 然后执行之前在i和N之间的搜索。