在O(logn)中解决代码的困难

Question

我写了一个函数,它按顺序获取一个唯一整数列表的输入(从小到大).我应该在列表中找到一个与索引中的值匹配的索引.例如,如果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

根据您给出的限制，这是不可能的。理论上可以实现的最佳复杂度是O (\xc2\xad n )。

\n\n

O () 假设最坏的情况（只是一个定义，您可以删除该部分）。在最坏的情况下，您始终必须查看每个项目以检查它是否等于其索引。

\n\n

如果您有更多限制，则情况会发生变化（例如，数字都是整数，并且不能出现多次，即没有两个连续数字相等）。或许是这样呢？

\n\n

编辑：

\n\n

在听说实际上我假设的限制适用（即仅出现一次的整数）之后，我现在提出这种方法：您可以安全地假设您只能拥有一个连续范围，其中所有匹配条目都位于其中。IE。您只需要找到下限和上限。想要的结果将是该范围的大小。

\n\n

每个边界都可以使用二分搜索安全地找到，其中每个边界的复杂度为O (log n )。

\n\n

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

\n\n

我用这个来测试：

\n\n

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

\n