搜索指针 i，其中 A[i]=i

Question

给定一个由不同整数组成的排序数组 A[1, . . . , n], 你想知道是否有 A[i] = i 的索引 i。给出一个运行s 时间 O(log n) 的分而治之算法。

到目前为止我想出的是一个修改后的二进制搜索，它将丢弃数组的右半部分，具体取决于对我们目前在二进制搜索中作为枢轴的元素的检查。

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(log n) 时间吗？如果不是，我应该怎么做才能在 O(log n)?

中实现运行

Answer 1

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

你至少需要记住两个变量和数组。这两个变量是 "min" 和 "max" 以了解您正在递归二进制搜索的数组边界。

将其视为字典中的列表。

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

你在第512页打开它，你发现"mom"，因此它必须在0 - 512之间。

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

之间

等等

这两个值是最小值和最大值，您必须在递归方法中将它们作为参数传递。

Answer 2

如果你的伪代码实际上是说我们传递一个数组给函数，我们可以在O(1)时间内得到它的子数组，那么时间复杂度确实是O(log n)，因为数组的大小每一步后（大约）缩小两倍。

Answer 3

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

你首先需要说明数组是sorted，整数是distinct。这意味着给定两个索引 (i, j)，其中 i < j，然后 A[i]+1 <= A[j]。反过来，这意味着 A[i]-i <= A[i+1]-(i+1).

从这句话你可以得出结论，通过使用递归，数组 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

我提前为荒谬的伪代码道歉。从技术上讲，您的算法在 O(logn) 时间内运行，因为每次都会截断一半列表（每次除以 2，所以我们得到对数基数 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)

搜索指针 i，其中 A[i]=i

Searching for pointer i where A[i]=i

arrays

algorithm

binary-search