给定排序整数数组，为A[i]=i编写一个基于分治的algo
给定：排序整数数组，整数都是不同的-没有重复。
问题：编写了一个基于分而治之的算法(在运行时尽可能好)，以检查数组中是否存在Ai=i索引i。
我想到了二进制搜索，这是O(logn)运行时的复杂性。有比这更快的东西吗？
回答 3
Stack Overflow用户
发布于 2017-06-03 18:57:48
对输入本身进行排序的要求是不够的。在输入数组中没有两个相等值的附加要求是能够使用二进制搜索的必要条件。
如果这不是条件，则不能使用二进制搜索，如以下示例所示(假设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，但是当没有匹配，并且数组很大时，通常会有一个早期退出循环。
Stack Overflow用户
发布于 2017-06-02 13:51:24
让我们看一个例子:假设所有指数(除k外)的Ai=i-1，其中Ak=k。只在一个地方采样数组并不能告诉你关于k的位置的任何信息(除非你碰巧碰上了k)。
因此，我认为您不可能得到比O(n)更糟糕的运行时。
Stack Overflow用户
发布于 2017-06-02 14:12:20
我认为最好使用二进制搜索
1)给出了排序整数
2)需要分而治之的算法
3)二进制搜索的运行时间为O(logn)，优于线性搜索。
https://stackoverflow.com/questions/44316145
复制相似问题
腾讯云开发者
