给定排序的整数数组，写一个基于分治法的算法 A[i]=i

Question

给定： 排序的整数数组，整数都是不同的 - 没有重复项。

问题：基于分治法写一个算法（在运行时间内尽可能好）检查是否有索引i满足A[i ]=i存在于数组中。

好吧，我想到了二进制搜索，它的时间复杂度为 O(logn) 运行。还有比这更快的吗？

Answer 1

让我们看一个例子：假设 A[i]=i-1 对于除 k 之外的所有索引，其中 A[k]=k。仅在一个位置对数组进行采样并不能告诉您有关 k 位置的任何信息（除非您碰巧碰巧碰上了 k）。

因此，我不认为您可以获得比 O(n) 更好的最坏情况运行时间。

Answer 2

我认为最好使用二进制搜索作为

1) 给你排序的整数

2) 你需要一个分而治之的算法

3) 运行二分查找时间复杂度为O(logn)，优于线性查找

Answer 3

输入排序本身的要求是不够的。输入数组中没有两个相等值的附加要求是能够使用二分查找的必要条件。

如果不是条件，则不能使用二进制搜索，如下例所示（假设 0 是第一个索引）：

    i:   0 1 2 3 4 5 6
        --------------
  A[i]: -1 0 x 4 y 6 7
               ^

通过二分搜索，您将获取中间元素并决定在它的哪一侧可能存在 i 和 A[i]=i。问题在于，在上面的示例中，解可能位于中心的任一侧：如果 x=2，则解在左侧，而当 y=4 时，解在右侧。所以分而治之是行不通的。只有在保证输入没有重复值的情况下，分而治之的算法才能起作用。

最重要的是，您可以立即排除第一个值大于 0 的输入数组，因为如果没有重复值，就无法实现 A[i]=i。同样，最后一个值小于最后一个索引的输入数组没有 i 和 A[i]=i.

这种考虑在分而治之期间也适用。举个例子：

    i:   0 1 2 3 4 5 6 7 8
        -------------------
  A[i]: -4 0 1 2 5 6 7 8 10

首先验证两端的两个值：它们不排除解决方案，因此采用索引 4 处的中间值。由于其值 (5) 大于索引 (4)，因此可以忽略索引 4 到 8 的范围。因此在算法的下一次迭代中，索引 0 和 3（包括在内）之间的范围被考虑。

但是最右边的索引 (3) 的值小于 3（它是 2）。根据上述规则，这意味着没有解决方案，因此算法可以就此停止：再划分也是徒劳的。

所以这是一个 JavaScript 实现：

function hasSelfReference(arr) {
    let last = arr.length - 1;
    if (last < 0 || arr[0] > 0 || arr[last] < last) return false;

    let first = 0;
    while (first < last) {
        let mid = (first + last) >> 1;
        if (arr[mid] < mid) {
            first = mid + 1;
            if (arr[first] > first) return false;
        } else if (arr[mid] > mid) {
            last = mid - 1;
            if (arr[last] < last) return false;
        } else 
            return true;
    }
    return arr[first] === first; // arr[first] may be undefined: not a problem in JS
}

console.log(hasSelfReference([3, 4, 5, 6])); // false
console.log(hasSelfReference([-4, -2, 1, 2, 7])); // false
console.log(hasSelfReference([-4, -2, 1, 3, 7])); // true
console.log(hasSelfReference([])); // false
console.log(hasSelfReference([-4, 0, 1, 2, 5, 6, 7, 8, 10])); // false

与通常的分而治之算法一样，这具有 O(logn)（最坏情况）时间复杂度。

当数组有匹配索引时，则迭代次数为logn，但没有匹配时，则数组很大，经常会提前退出循环。

给定排序的整数数组，写一个基于分治法的算法 A[i]=i

Given sorted integer array, write an algo based on divide and conquer for A[i]=i

arrays

algorithm

divide-and-conquer