我得到了以下的面试问题。
有一个n x n元素的数组。该数组部分排序，即第i行中最大的元素小于第i+1行中最小的元素。如何在O(n)的复杂度下找到给定的元素。
这是我的解决方案：
您应该前往第n/2行。从那里开始比较，例如您搜索100并且您看到的第一个数字是110，那么您知道它要么在这一行中，要么在上面的行中，现在您走n/4行，以此类推。
从评论中得知：
总体而言, 不是 O(n * log n) 吗？因为他必须在每个二进制搜索达到的行中进行解析, 因此线性搜索的数量与他将要扫描的行数相乘。- Martin Matysiak 5分钟前。
我不确定这是一个正确的解决方案。有没有更好的方法？
你的解决方案确实是O(n log n)，假设你搜索了解析的每一行。如果不搜索每一行，则无法准确执行二进制步骤。
O(n)解决方案:
选择第n/2行，而不是搜索整行，我们只需取前一行的第一个元素和下一行的第一个元素。 O(1)。
我们知道n/2行的所有元素必须在这些选定的值之间（这是关键观察）。 如果目标值位于区间内，则搜索所有三行（3 * O(n) = O(n)）。
如果我们的值超出了这个范围，那么按二分搜索的方式继续选择n/4（如果我们的值小于范围），并选择3n/4行（如果该值更大），然后再与相邻行的一个元素进行比较。
找到正确的3行块将花费O(1) * O(log n)，找到元素将花费O(n)。
总计O(log n) + O(n) = O(n)。
{ 1 2 3 ; 4 5 6 ; 8 7 9 }中搜索任何一个{2,5,7}都会发现目标确实在范围[1,8]内，但如果我不搜索所有3行，就找不到我需要的值之一。 - davin这里有一个简单的实现 - 因为我们无论如何需要在一行中查找元素的时间复杂度为O(n)，所以我省略了二分查找...
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);
}
}
}
}