算法分析 - 在排序数组中查找丢失的整数优于 O(n)

Question

我是第一次通过算法分析 class，想知道是否有人可以协助解决以下示例。我相信我已经解决了 O(n) 的复杂性，但想知道是否有更好的版本，我没有想到 O(logn)？

Let A= A[1] <= ... <= A[n+1] be a sorted array of n distinct integers, in which each integer is in the range [1...n+1]. That is, exactly one integer out of {1,...,n+1} is missing from A. Describe an efficeint algorithm to find the missing integer. Analyze the worst case complexity (number of accesses to array A) of your algorithm.

我的解决方案相对简单，我相信会导致最坏情况下的 N 复杂度。也许我想多了这个例子，但是有更好的解决方案吗？

我的解决方案

for(i = 1; i < n +1; i++) :
    if(A[i-1] > i) :
         return i

这背后的逻辑是因为它是排序的，第一个元素必须是1，第二个必须是2，依此类推，直到数组中的元素大于它应该的元素是，表示缺少一个元素，return 它应该是的元素，我们有丢失的元素。

这是正确的逻辑吗？有更好的方法吗？

感谢阅读并提前感谢您的帮助。

Answer 1

您可以使用 A[i] > i 对第一个索引 i 进行二进制搜索。如果缺少的整数是 k，那么 A[i] = i for i < k and A[i] = i + 1 for i >= k.

Answer 2

这个逻辑当然是正确的，但它的速度不足以击败 O(n)，因为你检查了每个元素。

您可以通过观察如果 A[i]==i，则 j < i 处的所有元素都在其正确的位置来更快地完成。这个观察应该足以构建一个在 O(log₂n):

中运行的分而治之的方法

检查中间的元素
如果走错了，往左走
否则向右走

更正式地说，您正在寻找 A[i]==i 和 A[i+1]==i+2 的位置。您从数组末端的间隔开始。间隔中间的每个探针都会将剩余间隔缩小两倍。在某些时候，您只剩下两个元素的间隔。左边的元素是最后一个"correct"元素，而右边的元素是缺号后的第一个元素

Answer 3

有时诀窍在于换个角度思考问题。

从本质上讲，您只是在处理一组布尔值；索引 n 处的条目是 a[n] > n.

的真实值

此外，这个数组以零个或多个连续的false开始，剩下的条目都是true.

你现在的问题是在（排序的）布尔值数组中找到 true 的第一个实例的索引。

算法分析 - 在排序数组中查找丢失的整数优于 O(n)

Analysis of Algorithms - Find missing Integer in Sorted Array better than O(n)

arrays

algorithm

sorting

asymptotic-complexity