在O（logn）中求解代码困难

Question

我编写了一个函数，它按顺序（从小到大）获取一个惟一int的列表作为输入。我应该在列表中找到一个与索引中的值相匹配的索引。例如，如果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

Answer 1

假设负整数正常：

我认为关键是如果你得到的值小于你的索引，你知道所有左边的索引也不匹配它们的值（因为整数是严格递增的）。另外，一旦得到一个值大于该索引的索引，右侧的所有内容都是不正确的（原因相同）。然后你可以做一个分而治之的算法，就像你在第一个例子中所做的那样。大致如下：

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)

在最坏的情况下（每个索引都与值匹配），我们仍然需要检查每个索引。在

如果整数是非负的，那么你知道得更多。现在您还知道，如果一个索引与该值匹配，则左侧的所有索引也必须与该值匹配（为什么？）。因此，您可以得到：

^{pr2}$

我们最坏的情况现在明显改善了。我们没有找到一个匹配的索引，也没有从中获取任何新的信息，而是在找到匹配的索引时获得大量信息，现在知道一半的索引匹配。在

Answer 2

你给的限制还不可能。理论上可以达到的最佳复杂度是O（…n）。在

O（）假设了最坏的情况（只是一个定义，你可以去掉这个部分）。在最坏的情况下，你总是要检查每个项目是否等于它的索引。在

如果你有更多的限制（例如，所有的数字都是整数，没有一个可以出现多次，即没有两个连续的数字是相等的）。也许是这样吧？在

编辑：

在听说事实上我假设的限制是适用的（即只出现一次int），我现在提出这个方法：您可以安全地假设只有一个连续的范围，所有匹配的条目都位于该范围内。一、 你只需要找到一个下界和上界。然后，想要的结果就是这个范围的大小。在

使用二进制搜索可以安全地找到每个边界，其中每个边界都有O（logn）。在

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

我用来测试：

^{pr2}$

Answer 3

如果“所有的数字都是int并且它们只出现一次”，那么您可以简单地对第一对数字进行二进制搜索，其中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之间执行前面的搜索