在A[i]=i处搜索指针i

Question

给定一个不同整数a[1，…，n]的排序数组，您想知道是否存在索引i，其中A[i]=i。给出一个在时间O（logn）中运行的分治算法。

到目前为止，我提出了一个修改后的二进制搜索，它将丢弃数组的右半部分，这取决于我们目前在二进制搜索中作为支点的元素的检查。

modifiedBinSearch(a[1],a[n]){
int i = a.length/2;
if(a[i]==i) return i;
if(i>a[i]) return ModifiedBinSearch(a[1],a[i]);
else return ModifiedBinSearch(a[i], a[n]);
}

此算法是否在O（logn）时间内运行？如果没有，我应该怎么做才能使它在O（logn）中运行？

Answer 1

我为这个荒谬的伪代码提前道歉。从技术上讲，您的算法在O(logn)时间内运行，因为每次都会截断一半的列表（每次除以2，所以我们得到log base 2）。然而，正如libik所指出的，a.length总是一样的，所以你不会有任何进展。您需要将索引作为参数传递。

func(a, lo, hi)
    len = hi - lo + 1
    mid = len / 2 + lo
    switch len, a[mid] > mid
        case 1, _: a[lo] = lo ? lo : -1
        case _, t: func(a, lo, mid - 1)
        case _, _: func(a, mid, hi)
func(arr, 0, arr.length - 1)

Answer 2

如果您的伪代码实际上意味着我们将一个数组传递给一个函数，并且我们可以在O(1)时间内获得它的子数组，那么时间复杂性实际上是O(log n)，因为数组的大小在每一步之后（近似地）会变小两倍。

Answer 3

让我们定义A为输入数组，N为该数组的长度。

您首先需要注意，数组是排序的，整数是distinct的。这意味着给定两个索引(i, j)，其中i < j，然后A[i]+1 <= A[j]。这反过来意味着CCD_。

根据这句话，您可以使用递归得出结论，数组B定义为：

For i in (0..N-1) B[i] = A[i]-i

也是一个排序数组。

您的伪代码只是一个二进制搜索，用于查找B中是否存在0。此值的索引是您要查找的索引。

二进制搜索具有O[log(n)]的复杂度。

注意：为什么我说伪代码是对值0的二进制搜索

只需更换条件：

• a[i] == i，带：a[i]-i == 0
• i > a[i]，带：a[i]-i < 0

注释2

伪代码不处理缺少值的情况。

Answer 4

您的alghoritm不工作，int i = a.length/2;这个值总是相同的，数组a的大小没有改变。

您确实需要记住至少两个变量和数组。这两个变量是"min"one_answers"max"，用来知道递归二进制搜索的数组的边界。

把它想象成字典里的列表。

例如，它有1024页，您正在查找单词"浆果"。

你在第512页打开它，你会发现"妈妈"，所以它必须在0-512之间。

所以你看看256，你会发现"alhocol"->它必须在256-512 之间

等等。

这两个值分别是min和max，您必须在递归方法中将它们作为参数传递。