arrays - 算法分析-在排序数组中找到比O(n)更好的缺失整数

我是第一次对算法类进行分析，想知道是否有人可以帮助以下示例。我相信我已经解决了O(n)复杂性的问题，但是想知道是否有一个我不考虑O(logn)的更好的版本？



我拥有的解决方案相对简单，并且我相信会导致最坏情况下的N复杂度。也许我正在考虑示例，但是有更好的解决方案吗？

我的解决方案

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

其背后的逻辑是，由于已对其进行排序，因此第一个元素必须为1，第二个元素必须为2，依此类推，依此类推，直到数组中的元素大于其应假定的元素为止，从而使一个元素独享被错过了，返回它应该是的元素，我们有一个缺失的元素。

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

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

最佳答案

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

通过观察A[i]==i，可以更快地完成此操作，然后j < i上的所有元素都在适当的位置。此观察结果应足以构建在O(log2n)中运行的分而治之的方法:

检查中间

中的元素

如果在错误的位置，请向左走

否则，请右转到

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

关于arrays - 算法分析-在排序数组中找到比O(n)更好的缺失整数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29872993/