c++ - 在部分排序的数组中查找元素

Question

我有以下面试问题。

有一个 nxn 元素的数组。数组是部分排序的，即行 i 中的最大元素小于行 i+1 中的最小元素。如何找到复杂度为 O(n) 的给定元素

这是我的看法:

您应该转到第 n/2 行。然后开始比较，例如，您搜索 100，您看到的第一个数字是 110，所以您知道它在这一行或上面的行中，现在您转到 n/4 等等开。

来自评论

Isn't it O(n * log n) in total? He has to parse through every row that he reaches per binary search, therefore the number of linear searches is multiplied with the number of rows he will have to scan in average. – Martin Matysiak 5 mins ago.

我不确定这是一个正确的解决方案。谁有更好的东西

Answer 1

您的解决方案确实需要O(n log n)假设您正在搜索解析的每一行。如果不搜索每一行，则无法准确执行二进制步骤。

O(n)解决方案:

选择n/2行，而不是搜索整行，我们只取上一行的第一个元素和下一行的第一个元素。 O(1) .
我们知道 n/2 的所有元素行必须在这些选定值之间(这是关键观察)。如果我们的目标值在区间内，则搜索所有三行 (3*O(n) = O(n))。

如果我们的值在这个范围之外，那么通过选择n/4继续以二分查找方式。如果我们的值小于范围，并且 3n/4如果值更大，则行，然后再次与相邻行的一个元素进行比较。

找到正确的 3 行 block 将花费 O(1) * O(log n) , 并且找到该元素将花费 O(n) .

总计 O(log n) + O(n) = O(n) .