在一个已排序的数组中，找到满足a[i]=i的最有效方法是什么？

Question

给定一个数组a[]，最有效的方法是确定是否至少有一个元素i满足条件a[i] == i?

数组中的所有元素都已排序且不重复，但它们不一定是整数类型（即它们可能是浮点类型）。

- k53sc

---

找出是否存在任何一个元素，其满足 a[i] = i。 - k53sc

@axiom：我猜他指的是 a[] ... - Guy Sirton

给定一个数组，您需要知道是否存在任何一个元素的值与其索引匹配，数组已排序对此无帮助，我认为提供这一信息只是稍微转移注意力。最好的算法是线性的，检查每个索引处存储的值是否与该索引匹配。 - Chad

@Chad：如果数组是整数，那么将其排序会稍微有些好处。如果a[i]>i，则可以立即知道对于任何j>i都没有匹配项。您可以采用分而治之的方法，尝试拒绝尽可能多的元素。但是，OP说a[]可以是非整数，因此这并没有帮助。 - Guy Sirton

@GuySirton 对于整数值，“轻微好处”是一种低估。O(n) 和 O(log n) 之间的差异非常显著。 - Daniel Fischer

Answer 1

几个人提出了“排序”、“不同”和“不一定是整数”的相关性的主张。事实上，选择有效算法来解决这个问题取决于这些特征。如果我们知道数组中的值既是不同的又是整数，那么更有效率的算法就是可能的，而如果值可能是非不同的，无论它们是否是整数，就需要更低效的算法。当然，如果数组没有被排序过，你可以首先对它进行排序（平均复杂度为O(n log n)），然后使用更有效的预排序算法（即对于已排序的数组），但在未排序的情况下，直接线性比较数组中的值会更有效率（O(n)）。请注意，无论选择哪种算法，最好情况下的性能都是O(1)（当第一个被检查的元素包含其索引值时）；在任何算法执行过程中，我们可能会遇到一个元素，其中a[i] == i，此时我们返回true；在这个问题中，实际上重要的是我们如何快速排除所有元素并声明不存在这样的元素a[i]，其中a[i] == i。

问题没有说明 a[] 的排序顺序，这是一条非常重要的遗漏信息。如果是升序，最坏情况复杂度始终为 O(n)，我们无法做出任何改进来使最坏情况复杂度更好。但是如果排序顺序是降序，即使最坏情况下复杂度也是 O(log n)：由于数组中的值是不同的并且是降序的，只有一个可能的索引位置可以使 a[i] 等于 i，基本上您只需要进行二分查找以找到交叉点（如果存在这样的交叉点，则升序索引值会越过降序元素值），并确定交叉点索引值 c 处的 a[c] == c。由于这很简单，我将继续假设排序顺序为升序。有趣的是，如果元素是整数，在升序情况下也存在类似“交叉点”的情况（尽管在升序情况下可能会有多个 a[i] == i 匹配项），因此如果元素是整数，则二分查找也适用于升序情况，在这种情况下，即使最坏情况下性能也将是 O(log n)（参见 Interview question - Search in sorted array X for index i such that X[i] = i）。但在这个版本的问题中，我们没有得到这种奢侈。

这里是我们可能解决这个问题的方法：

从第一个元素 a[0] 开始。如果它的值为 == 0，则找到了满足条件 a[i] == i 的元素，返回 true。如果它的值为 < 1，下一个元素 (a[1]) 可能包含值 1，因此继续到下一个索引。然而，如果 a[0] >= 1，你知道（因为值是不同的）条件 a[1] == 1 不可能成立，所以可以安全地跳过索引 1。但你甚至可以做得更好：例如，如果 a[0] == 12，你知道（因为值按升序排序）在元素 a[13] 之前不能有任何满足条件 a[i] == i 的元素。因为数组中的值可以是非整数，所以我们在这一点上不能作出进一步的假设，因此我们可以直接跳过到下一个安全的元素，即 a[13]（例如，a[1] 到 a[12] 可能都包含介于 12.000... 和 13.000... 之间的值，使得 a[13] 仍然可能恰好等于 13，因此我们必须检查它）。

继续这个过程得到以下算法：

// Algorithm 1
bool algorithm1(double* a, size_t len)
{
    for (size_t i=0; i<len; ++i) // worst case is O(n)
    {
        if (a[i] == i)
            return true; // of course we could also return i here (as an int)...
        if (a[i] > i)
            i = static_cast<size_t>(std::floor(a[i]));
    }
    return false; // ......in which case we’d want to return -1 here (an int)
}

如果数组中许多值都大于它们的索引值，此算法性能良好；如果所有值都大于n，性能优秀（仅需一次迭代即可返回false）；但是，如果所有值都小于它们的索引值，性能极差（需要n次迭代才能返回false）。因此我们需要重新考虑…但我们只需要稍微改进一下。请注意，该算法也可以从n向下逆向扫描，就像从0到n正向扫描一样容易。如果我们将从两端向中间迭代的逻辑结合起来，就得到了以下算法：

// Algorithm 2
bool algorithm2(double* a, size_t len)
{
    for (size_t i=0, j=len-1; i<j; ++i,--j) // worst case is still O(n)
    {
        if (a[i]==i || a[j]==j)
            return true;
        if (a[i] > i)
            i = static_cast<size_t>(std::floor(a[i]));
        if (a[j] < j)
            j = static_cast<size_t>(std::ceil(a[j]));
    }
    return false;
}

该算法在两种极端情况下具有出色的性能（所有值都小于0或大于n），并且在几乎任何其他值的分布情况下都具有相当好的性能。最坏情况是，如果数组的下半部分中的所有值都小于它们的索引，并且上半部分中的所有值都大于它们的索引，则性能会降至 O(n) 的最坏情况。最佳情况（任一极端情况）为O(1)，而平均情况可能是 O(log n)，但我还是会请一个数学专业的人来确定这一点。

几个人建议采用“分而治之”的方法来解决问题，但没有说明如何划分问题以及如何处理递归划分的子问题。当然，这种不完整的答案可能无法满足面试官的要求。Naïve线性算法和算法2的最坏情况性能都是O(n)，而算法2通过跳过（不检查）尽可能多的元素来改善平均情况性能，可能达到O(logn)。只有在平均情况下，“分而治之”方法才能优于算法2，如果它可以比算法2更多地跳过元素。假设我们将问题通过将数组分成两个（几乎）相等的连续段进行递归分割，并决定是否能够使用所得到的子问题跳过比算法2更多的元素，特别是在算法2的最坏情况下。在本讨论的其余部分，假设输入是算法2的最坏情况。在第一次拆分后，我们可以检查两个部分的顶部和底部元素，以获得算法2的O(1)性能极端情况，但结合两个部分时却会导致O(n)性能。如果底部的所有元素都小于0，而上半部分的所有元素都大于n-1，则会出现这种情况。在这些情况下，我们可以立即排除底部和/或顶部的一半，并为任何可以排除的一半提供O(1)的性能。当然，对于无法通过该测试排除的任何一半的性能仍需进一步确定，在进一步递归分割该一半，直到找到其顶部或底部元素包含其索引值的段。这是相比算法2一个相当不错的性能提升，但它只发生在算法2最坏情况的特定情况下。"分而治之"方法所做的一切都仅仅是稍微减少了引起最坏情况行为的问题空间的比例。对于"分而治之"也仍有最坏情况的场景，它们恰好与算法2引起最坏情况行为的大多数问题空间相匹配。

因此，考虑到分治算法具有更少的最坏情况，使用分治方法是有意义的吗？

总之，不是。嗯，也许吧。如果你事先知道大约一半的数据小于0，另一半大于n，那么这种特殊情况通常会使用分治方法更好。或者，如果您的系统是多核心的，而且n很大，将问题平均分配给所有核心可能会有所帮助，但一旦它们被分配，我认为每个核心上的子问题最好使用上面的算法2来解决，避免进一步分割问题，当然也要避免递归，就像我下面所说的那样...

在递归分治算法的每个递归层次中，算法需要一些方法来记住尚未解决的问题的第二部分，同时递归到第一部分。通常，这是通过让算法先递归调用自身处理一半的问题，然后再处理另一半的方式实现的，这种设计在运行时堆栈上隐式地维护了这些信息。另一种实现可能会避免使用递归函数调用，而是在显式堆栈上维护基本相同的信息。就空间增长而言，算法2是O（1），但任何递归实现都无法避免由于必须在某种类型的堆栈上维护此信息而导致的O（log n）。但除了空间问题外，递归实现还有额外的运行时开销，需要记住尚未递归进去的子问题的状态，直到可以递归为止。这种运行时开销不是免费的，鉴于上述算法2的简单实现，我认为这样的开销在比例上是相当显著的。因此，我建议对于绝大多数情况，算法2将轻松击败任何递归实现。

- phonetagger

Answer 2

在最坏的情况下，只能检查每个元素以确保正确性。（想象一下这样的情况：a[i] = i + uniform_random(-.25, .25)。）你需要了解输入数据的形式。

- tmyklebu

---

有一些情况可以改进这个算法。例如，如果你有一个包含100个元素的数组，索引从0到99，而中间元素包含100，那么由于数组已经排序，你知道可以跳过数组的后半部分。但是，最坏情况下的时间复杂度仍然是线性的。 - Thomas Padron-McCarthy

@k53sc 是的，O(n) 因为它对数组进行了一次完整遍历。 - Mike

Answer 3

实际上，我会从最后一个元素开始，进行基本检查（例如，如果您有1000个元素，但最高的是100，您就知道只需要检查0..100）。在最坏的情况下，您仍然需要检查每个元素，但应该更快地找到可能存在问题的区域。如果如上所述（a[i] = i + [-0.25..0.25]），那么你就很麻烦了，需要搜索每个单独的元素。

- SinisterMJ

Answer 4

注意到数组中的所有元素都是排序且不重复的，因此如果我们构造一个新数组b，其中b[i] = a[i] - i，那么数组b中的元素也是有序的，我们需要找到的是在数组b中找到零值。我认为二分查找可以解决这个问题！以下是一个link用于计算已排序数组中出现次数的链接。您还可以对原始数组执行类似的分治技术而无需构建辅助数组！时间复杂度为O（Logn）！

Take this as an example:
a=[0,1,2,4,8]
b=[0,0,0,1,4]
What we need to find is exactly index 0,1,2

希望能对你有所帮助！

- Chasefornone

Answer 5

我认为这里的主要问题是您的陈述存在冲突：

a[i] == i

数组中的所有元素都是排序且不重复的，它们不一定总是整数。

如果数组的值等于其访问下标，那么它就是一个整数。如果它不是整数，而是例如字符（char），那么什么被认为是“排序”的？ASCII 值（A < B < C）吗？

如果它是一个字符数组，我们会考虑：

a[i] == i

如果

i == 65₁₀ && a[i] == 'A'

如果我在这个面试中，我会在回答之前向面试官提出跟进问题。话虽如此...

如果我们所知道的只是您所陈述的内容，那么我们可以安全地说，我们可以在O(n)的时间内找到该值，因为这是遍历整个数组的时间。通过更多的细节，我们可能可以通过对数组进行二分查找将其限制为O(log(n))。

- Mike

Answer 6

对于一个有序数组，可以进行插值搜索。类似于二分查找，但是假设值的分布均匀，可以更快。

- Rahul Tripathi

---

我认为这对于非整数值的情况不起作用。在选择中点（无论是通过一半、插值还是掷骰子）之后，仅根据中点值仍然不知道要丢弃哪个段。 - Robᵩ