提问人：YAKOVM 提问时间：6/4/2011 最后编辑：YAKOVM 更新时间：6/14/2014 访问量：1733
在部分排序的数组中查找元素
Finding an element in partially sorted array
问：
我有一个以下面试问题。
有一个 nxn 元素数组。数组是部分排序的，即行中最大的元素小于行中最小的元素。
如何找到复杂度为 O（n） 的给定元素ii+1
以下是我对此的看法：
你应该去行 n/2.然后开始比较，例如，你搜索 100，你看到的第一个数字是 110，所以你知道它要么在这一行，要么在上面的行中，现在你去 n/4，依此类推。
从评论
总共不是O（n * log n）吗？他有 解析他的每一行 因此，每个二进制搜索的覆盖率 线性搜索的次数为 乘以 he 的行数 平均必须扫描。–马丁 Matysiak 5分钟前。
我不确定这是否是正确的解决方案。有没有人有更好的东西
答：
15赞
davin
6/4/2011
#1
您的解决方案确实需要假设您正在搜索您解析的每一行。如果不搜索每一行，则无法准确执行二进制步骤。O(n log n)
O(n)溶液：
选择行，而不是搜索整行，我们只需获取上一行的第一个元素和下一行的第一个元素。.
我们知道，行的所有元素都必须在这些选定的值之间（这是关键观察结果）。如果我们的目标值位于区间内，则搜索所有三行 （）。n/2O(1)n/23*O(n) = O(n)
如果我们的值超出此范围，则继续以二进制搜索方式，选择我们的值是否小于该范围，如果值大于该值，则选择行，并再次与相邻行的一个元素进行比较。n/43n/4
找到正确的 3 行块将花费 ，而找到元素将花费 。O(1) * O(log n)O(n)
总共.O(log n) + O(n) = O(n)
评论
0赞
dcn
6/4/2011
实际上，通过搜索行并与行的第一个（或任何）值进行比较，您可以将可能的行限制为 2 而不是 3。
0赞
davin
6/4/2011
@dcn，不是真的。 搜索任何一个都会产生目标确实在范围内，但要找到我需要搜索所有 3 行的值，如果我不这样做，我不会找到其中一个值。{ 1 2 3 ; 4 5 6 ; 8 7 9 }{2,5,7}[1,8]
0赞
dcn
6/4/2011
不。搜索“2”。与“5”相比，它更大 -> 只能在第 1 行和第 2 行。同样的论点也适用于搜索 5 和 7。
0赞
dcn
6/4/2011
我的错。我以为您正在与连续行中的元素进行比较，但是再读一遍，上一个和下一个不应该是邻居。
2赞
dcn
6/4/2011
当然，您可以将其减少到 2 个可能的行，如下所示：通过 binsearch，您可以找到行的最小索引 maxrow ，这样 maxrow 的第一个元素就比您要查找的元素大。那么只有 maxrow 和 maxrow-1 是候选者
3赞
dcn
6/4/2011
#2
这是一个简单的实现 - 由于我们需要 O（n） 来查找行中的元素，因此我省略了 bin-search......
void search(int n[][], int el) {
int minrow = 0, maxrow;
while (minrow < n.length && el >= n[minrow][0])
++minrow;
minrow = Math.max(0, minrow - 1);
maxrow = Math.min(n.length - 1, minrow + 1);
for (int row = minrow; row <= maxrow; ++row) {
for (int col = 0; col < n[row].length; ++col) {
if (n[row][col] == el) {
System.out.printf("found at %d,%d\n", row, col);
}
}
}
}
评论
0赞
j_random_hacker
6/5/2011
起初我很困惑你为什么在行中使用线性搜索，但后来一分钱掉了......O（n） + O（n） = O（log n） + O（n） = O（n），所以如果你不需要，为什么要花哨！:)（当然，如果它是一个 m*n 矩阵，那么为了实现最佳，你毕竟需要二进制搜索......
0赞
Neel
5/10/2013
@dcn - 您能解释一下 minrow 和 maxrow 计算背后的逻辑吗？
评论