查找等于数组（已排序）值的索引的时间复杂度

Question

这种递归类似于二进制搜索，但我不确定如何使用反向替换来准确解决递归。

要找到等于数组值的索引（在排序数组中），代码基本上如下所示：

find(array, low, high) {
    if high < low
         return -1

    mid = (low + high) / 2
    midval = array[mid]

    if midval == mid
        return mid

    int left = find(array, low, min - 1)
    if left >= 0
        return left

    int right = find(array, mid + 1, high)
    return right
}

因此递推关系如下所示：

T(1) = b

T(n) = 2T(n/2) + c
     = 4T(n/4) + c(1+2)
     = 8T(n/8) + c(1+2+4)
     = 16(n/16) + c(1+2+4+8)

     = 2^k T(n/2^k) + (2^k - 1)c
     = 2^(logn)T(1) + (2^(logn) - 1)c
     = 2^(logn)(1+c) - c

我知道时间复杂度应该是 O(logn) 或 O(nlogn)，但我不确定如何使用反向替换来实现这一目标。

Answer 1

对于排序数组，查找具有天真的实现的元素最差 O(n)。因此，更好的方法的最坏情况复杂度低于 O(n)，因此它不能是 O(n logn).

在典型的二分搜索中，人们利用正在排序的数组，因此不需要为每个递归调用在两个子树中搜索。一个在阵列上向左或向右移动。所以 T(n) = 2T(n/2) + c 应该是 T(n) = T(n/2) + c.

现在你的问题不同于二分查找，因为你想在数组中找到与其索引值匹配的位置。因此，与此上下文中的二进制搜索不同，您可能还必须在某些递归调用中同时向右和向左移动。

所以在你的情况下，最坏的情况实际上是 O(N)，因为 2^(log2N) 是 N，如你所见 here。除非有一种超级聪明的方法来改进您的代码，否则我只会进行常规搜索，更简单且更易读的代码也适用于 O(N) 的最坏情况。

如果值 x 与您 return 该值的索引匹配，则您从数组的开头搜索。否则，如果 x > the current index，您可以跳转到下一个等于值 x 的索引（，即 array[x]），从而跳过数组位置基于数组已排序的事实，将没有与其值匹配的索引。

查找等于数组（已排序）值的索引的时间复杂度

Time complexity of finding index equal to array (sorted) value

arrays

algorithm

time-complexity