给定一个二维数组按从左到右和从上到下的顺序sorting，search目标数字的最佳方法是什么？

最近我接受了这个面试问题，我很好奇这是一个很好的解决scheme。

说我给了一个二维数组，其中所有数字中的数字从左到右，从上到下依次递增。

search和确定目标号码是否在arrays中的最佳方法是什么？

现在，我的第一个倾向是利用二进制search，因为我的数据是sorting的。 我可以确定一个数字是否在O（log N）时间的单行中。 然而，这是2个方向，把我扔掉。

我认为可能的另一个解决scheme是从中间的某个地方开始。 如果中间值小于我的目标，那么我可以确定它是在matrix的左边的中间部分。 然后我再进行诊断并再次检查，减less了目标可能在的方格的大小，直到我磨练了目标数字。

有没有人有解决这个问题的好主意？

示例数组：

从左到右，从上到下排列。

1 2 4 5 6 2 3 5 7 8 4 6 8 9 10 5 8 9 10 11 

Answer 1

这是一个简单的方法：

1. 从左下angular开始。
2. 如果目标值低于这个值，它必须高于我们，所以向上移动一个 。
3. 否则，我们知道目标不能在该列中，所以向右移动一个 。
4. 转到2。

对于一个NxMarrays，这个运行在O(N+M) 。 我认为要做得更好会很困难。 🙂

---

编辑：很多很好的讨论。 我在谈论上面的一般情况， 显然，如果N或M很小，那么可以使用二分search方法在接近对数时间的情况下执行此操作。

以下是一些细节，对于那些好奇的人来说：

历史

这个简单的algorithm被称为Saddlebacksearch 。 已经有一段时间了，当N == M时是最佳的。 一些参考：

• 大卫格里斯， 编程科学 。 Springer-Verlag，1989 。
• Edsgar Dijkstra，马鞍形search 。 注意EWD-934,1985 。

然而，当N < M ，直觉表明二分search应该能够比O(N+M)做得更好：例如，当N == 1 ，纯二分search将以对数而不是线性时间运行。

最坏的情况

理查德·伯德（Richard Bird）研究了这种直觉：二元search可以在2006年的一篇论文中改进马鞍algorithm：

• Richard S. Bird，“ 改进鞍座search：algorithmdevise的一课” ，程序构buildmath，第82-89页，第4014卷，2006年 。

Bird用非常不寻常的会话技术向我们展示了对于N <= M ，这个问题具有Ω(N * log(M/N))的下限。 这个界限是有意义的，因为当N == 1时，它使我们具有线性性能，而当N == 1时，它对数性能。

矩形arrays的algorithm

一种使用逐行二进制search的方法如下所示：

1. 从N < M的矩形arrays开始。 比方说， N是行， M是列。
2. 在中间行进行二进制search以获取value 。 如果我们find了，我们就完成了。
3. 否则，我们find了一对相邻的数字s和g ，其中s < value < g 。
4. 上面和左边的数字的矩形小于value ，所以我们可以消除它。
5. g下面和右边的矩形大于value ，所以我们可以消除它。
6. 对于其余两个矩形的每一个，转到步骤（2）。

就最坏情况复杂性而言，该algorithm通过log(M)工作来消除一半可能的解决scheme，然后在两个较小的问题上recursion调用两次。 我们不得不为每行重复一个较小版本的log(M)工作， 但是如果行数与列数相比较小，那么能够在对数时间内消除所有这些列开始变得有价值 。

这给出了algorithm复杂度为T(N,M) = log(M) + 2 * T(M/2, N/2) ，Bird显示为O(N * log(M/N)) 。

Craig Gidney发表的另一种方法描述了一种类似于上述方法的algorithm：它使用M/N的步长一次检查一行。 他的分析表明，这也导致了O(N * log(M/N))performance。

性能比较

大O分析是一切都很好，但这些方法在实践中有多好？ 下面的图表为越来越多的“方形”数组检查了四种algorithm：

（“朴素”algorithm简单地search数组中的每一个元素，上面描述了“recursion”algorithm，“混合”algorithm是Gidneyalgorithm的一个实现，对于每个数组大小， 1,000,000个随机生成的数组。）

一些值得注意的地方：

• 正如预期的那样，“二分查找”algorithm在矩形arrays上提供了最好的性能，Saddlebackalgorithm在方阵上的效果最好。
• Saddlebackalgorithm比1-d数组的“朴素”algorithm性能更差，大概是因为它对每个项目进行了多重比较。
• “二进制search”algorithm在方阵上的性能大概是由于重复二进制search的开销造成的。

概要

聪明地使用二进制search可以为矩形和方形arrays提供O(N * log(M/N)性能O(N + M) “鞍形”algorithm非常简单，但随着arrays变得越来越长。

Answer 2

这个问题需要Θ(b lg(t))时间，其中b = min(w,h)和t=b/max(w,h) 。 我在这篇博客文章中讨论解决scheme。

下界

对手可以迫使一个algorithm通过限制自己到主对angular线来进行Ω(b lg(t))查询：

图例：白色的细胞是较小的项目，灰色的细胞是较大的项目，黄色的细胞是较小或相等的项目和橙色的细胞是大于或等于项目。 对手迫使解决scheme是algorithm查询最后的黄色或橙色单元格。

请注意，有大小为t b独立分类列表，要求Ω(b lg(t))查询完全消除。

algorithm

1. （假定不失一般性， w >= h ）
2. 将目标物品与有效区域右上angular左侧的单元格t进行比较
   • 如果单元格的项目匹配，则返回当前位置。
   • 如果单元格的项目小于目标项目，则使用二分search消除行中剩余的t单元格。 如果在执行此操作时find匹配的项目，请返回其位置。
   • 否则，单元格的项目比目标项目多，消除了短列。
3. 如果没有有效区域，则返回失败
4. 转到第2步

查找项目：

确定一个项目不存在：

图例：白色细胞是较小的项目，灰色细胞是较大的项目，绿色细胞是一个相同的项目。

分析

有b*t短列消除。 有b长行消除。 消除长行花费O(lg(t))时间。 消除短柱的成本为O(1)次。

在最坏的情况下，我们必须消除每一列和每一行，花费时间O(lg(t)*b + b*t*1/t) = O(b lg(t)) 。

请注意，我假设lg钳位结果高于1（即lg(x) = log_2(max(2,x)) ）。 这就是为什么当w=h ，意味着t=1 ，我们得到O(b lg(1)) = O(b) = O(w+h)的期望界限。

码

 public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) { if (grid == null) throw new ArgumentNullException("grid"); comparer = comparer ?? Comparer<T>.Default; // check size var width = grid.Count; if (width == 0) return null; var height = grid[0].Count; if (height < width) { var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer); if (result == null) return null; return Tuple.Create(result.Item2, result.Item1); } // search var minCol = 0; var maxRow = height - 1; var t = height / width; while (minCol < width && maxRow >= 0) { // query the item in the minimum column, t above the maximum row var luckyRow = Math.Max(maxRow - t, 0); var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]); if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow); // did we eliminate t rows from the bottom? if (cmpItemVsLucky < 0) { maxRow = luckyRow - 1; continue; } // we eliminated most of the current minimum column // spend lg(t) time eliminating rest of column var minRowInCol = luckyRow + 1; var maxRowInCol = maxRow; while (minRowInCol <= maxRowInCol) { var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2; var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]); if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid); if (cmpItemVsMid > 0) { minRowInCol = mid + 1; } else { maxRowInCol = mid - 1; maxRow = mid - 1; } } minCol += 1; } return null; } 

Answer 3

对于这个问题，我会用分而治之的策略，就像你所说的那样，但细节有点不一样。

这将是matrix的子范围的recursionsearch。

在每一步中，select一个在范围中间的元素。 如果find的价值是你正在寻找的，那么你就完成了。

否则，如果find的值小于您正在查找的值，那么您知道它不在上面的象限中，并且不在当前位置的左侧。 因此，recursion地search两个子范围：当前位置以下的所有内容（全部），以及在当前位置或之上的所有内容（唯一）。

否则，（发现的值大于您正在查找的值），您知道它不在下面的象限中，并且位于当前位置的右侧。 因此，recursion地search两个子范围：当前位置左侧的所有内容（全部），以及当前位置上的所有内容（仅限于当前位置）或右侧列。

而巴达冰，你find了。

请注意，每个recursion调用只处理当前子范围，而不是（例如）当前位置上方的所有行。 只是在目前的子范围内。

这里有一些伪代码给你：

 bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY) if (minX == maxX and minY == maxY and arr[minX,minY] != value) return false if (arr[minX,minY] > value) return false; // Early exits if the value can't be in if (arr[maxX,maxY] < value) return false; // this subrange at all. int nextX = (minX + maxX) / 2 int nextY = (minY + maxY) / 2 if (arr[nextX,nextY] == value) { print nextX,nextY return true } else if (arr[nextX,nextY] < value) { if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY)) return true return numberSearch(arr, value, nextX + 1, maxX, minY, nextY) } else { if (numberSearch(arr, value, minX, nextX - 1, minY, maxY)) return true reutrn numberSearch(arr, value, nextX, maxX, minY, nextY) } 

Answer 4

到目前为止，两个主要的答案似乎是O(log N) “ZigZag方法”和O(N+M)二进制search方法。 我想我会做一些testing比较两种方法与一些不同的设置。 以下是详细信息：

这个数组在每次testing中都是N×N的正方形，N从125到8000（我的JVM堆可以处理的最大）变化。 对于每个数组大小，我select了一个随机的地方放在一个单一的2 。 然后，我把每个可能的3 （到2的右侧和下面），然后用1填充其余的数组。 一些较早的评论者似乎认为这种types的设置会产生两种algorithm的最坏情况运行时间。 对于每个数组的大小，我挑选了2个（search目标）的100个不同的随机位置并运行testing。 我logging了每个algorithm的平均运行时间和最坏情况运行时间。 因为发生得太快而无法在Java中读取好的ms读数，并且因为我不信任Java的nanoTime（），所以我重复每次testing1000次，以便为所有时间添加统一的偏差因子。 结果如下：

ZigZag在平均和最差情况下的每个testing中都能够保持二进制，但是它们的差异都在一个数量级内。

这里是Java代码：

 public class SearchSortedArray2D { static boolean findZigZag(int[][] a, int t) { int i = 0; int j = a.length - 1; while (i <= a.length - 1 && j >= 0) { if (a[i][j] == t) return true; else if (a[i][j] < t) i++; else j--; } return false; } static boolean findBinarySearch(int[][] a, int t) { return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1); } static boolean findBinarySearch(int[][] a, int t, int r1, int c1, int r2, int c2) { if (r1 > r2 || c1 > c2) return false; if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false; if (a[r1][c1] > t) return false; if (a[r2][c2] < t) return false; int rm = (r1 + r2) / 2; int cm = (c1 + c2) / 2; if (a[rm][cm] == t) return true; else if (a[rm][cm] > t) { boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1); boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2); return (b1 || b2); } else { boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2); boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2); return (b1 || b2); } } static void randomizeArray(int[][] a, int N) { int ri = (int) (Math.random() * N); int rj = (int) (Math.random() * N); a[ri][rj] = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == ri && j == rj) continue; else if (i > ri || j > rj) a[i][j] = 3; else a[i][j] = 1; } } } public static void main(String[] args) { int N = 8000; int[][] a = new int[N][N]; int randoms = 100; int repeats = 1000; long start, end, duration; long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE; long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE; long zigSum = 0, zigAvg; long binSum = 0, binAvg; for (int k = 0; k < randoms; k++) { randomizeArray(a, N); start = System.currentTimeMillis(); for (int i = 0; i < repeats; i++) findZigZag(a, 2); end = System.currentTimeMillis(); duration = end - start; zigSum += duration; zigMin = Math.min(zigMin, duration); zigMax = Math.max(zigMax, duration); start = System.currentTimeMillis(); for (int i = 0; i < repeats; i++) findBinarySearch(a, 2); end = System.currentTimeMillis(); duration = end - start; binSum += duration; binMin = Math.min(binMin, duration); binMax = Math.max(binMax, duration); } zigAvg = zigSum / randoms; binAvg = binSum / randoms; System.out.println(findZigZag(a, 2) ? "Found via zigzag method. " : "ERROR. "); //System.out.println("min search time: " + zigMin + "ms"); System.out.println("max search time: " + zigMax + "ms"); System.out.println("avg search time: " + zigAvg + "ms"); System.out.println(); System.out.println(findBinarySearch(a, 2) ? "Found via binary search method. " : "ERROR. "); //System.out.println("min search time: " + binMin + "ms"); System.out.println("max search time: " + binMax + "ms"); System.out.println("avg search time: " + binAvg + "ms"); } } 

Answer 5

这是问题的下限的简短certificate。

你不能做比线性时间更好的（数组维数，而不是元素数）。 在下面的数组中，标记为*每个元素可以是5或6（与其他元素无关）。 所以如果你的目标值是6（或5），algorithm需要检查所有这些。

 1 2 3 4 * 2 3 4 * 7 3 4 * 7 8 4 * 7 8 9 * 7 8 9 10 

当然这也扩展到更大的arrays。 这意味着这个答案是最佳的。

更新：正如Jeffrey L Whitledge指出的那样，它只是运行时间与input数据大小（作为单个variables处理）的渐近下界的最佳值。 将运行时间视为两个数组维度上的双variables函数可以得到改善。

Answer 6

我想这是答案，它适用于任何种类的sortingmatrix

 bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key) { if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false; if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false; if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false; if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true; int xnew = (xmin + xmax)/2; int ynew = (ymin + ymax)/2; if (arr[xnew][ynew] == key) return true; if (arr[xnew][ynew] < key) { if (findNum(arr,xnew+1,xmax,ymin,ymax,key)) return true; return (findNum(arr,xmin,xmax,ynew+1,ymax,key)); } else { if (findNum(arr,xmin,xnew-1,ymin,ymax,key)) return true; return (findNum(arr,xmin,xmax,ymin,ynew-1,key)); } } 

Answer 7

有趣的问题。 考虑这个想法 – 创build一个边界，其中所有数字都大于您的目标，另一个数字小于您的目标。 如果两者之间留有任何东西，那就是你的目标。

如果我在你的例子中寻找3，我读第一行，直到我打到4，然后寻找最小的相邻数（包括对angular线）大于3：

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

现在我对小于3的数字也是这样做的：

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

现在我问，这两个边界内有什么东西？ 如果是的话，一定是3.如果不是，那么就没有3.间接的sorting，因为我实际上没有find这个数字，我只是推断它必须在那里。 这是所有3的计数额外的奖金。

我试过这个例子，它似乎工作正常。

Answer 8

通过arrays的对angular线进行二进制search是最好的select。 我们可以找出元素是否小于或等于对angular元素。

Answer 9

A.在目标号码可能在的那些行上进行二分search。

B.把它作为一个图：find一个总是最小的未访问的邻居节点和回溯时发现一个太大的数字

Answer 10

二进制search将是最好的方法，即时通讯。 从1/2 x开始，1/2 y将会减半。 IE 5×5广场将像x == 2 / y == 3一样。 我把一个价值降到了一个价值，在目标价值的方向上达到了更好的区域。

为了清楚起见，下一次迭代会给你一些像x == 1 / y == 2或者x == 3 / y == 5的东西

Answer 11

那么，首先，让我们假设我们正在使用一个正方形。

 1 2 3 2 3 4 3 4 5 

1.search广场

我会在对angular线上使用二进制search。 目标是find并非严格低于目标数字的较小数字。

说我正在寻找4例如，然后我会最终定位5 (2,2) 。

那么，我确信，如果4在表格中，则它位于(x,2)或(2,x)其中x在[0,2] 。 那么，这只是2个二进制search。

复杂性并不令人望而生畏： O(log(N)) （在长度为N范围内进行3次二分search）

2.寻找一个矩形，天真的方法

当然，当N和M不同（用一个矩形）时，它会变得更复杂，考虑这个退化的情况：

 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

假设我正在寻找9 …对angular线的方法仍然是好的，但对angular线变化的定义。 这里我的对angular线是[1, (5 or 6), 17] 。 假设我拿起[1,5,17] ，那么我知道如果9在表中，它是在子部分：

  5 6 7 8 6 7 8 9 10 11 12 13 14 15 16 

这给了我们2个矩形：

 5 6 7 8 10 11 12 13 14 15 16 6 7 8 9 

所以我们可以recursion！ 可能是从元素较less的元素开始的（尽pipe在这种情况下它杀死了我们）。

我应该指出，如果其中一个维度小于3 ，我们不能应用对angular线方法，并且必须使用二分查找。 这意味着：

• 在10 11 12 13 14 15 16上应用二进制search，找不到
• 在5 6 7 8上应用二进制search，找不到
• 在6 7 8 9应用二进制search，找不到

这是棘手的，因为得到良好的性能，你可能要区分几种情况，这取决于一般的形状….

3.search一个矩形，粗暴的方法

如果我们处理一个方块会容易得多…所以我们只是把它们放在一起。

 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 . . . . . . 17 . . . . . . 17 . . . . . . 17 

我们现在有一个广场。

当然，我们可能不会真的创build这些行，我们可以简单地模拟它们。

 def get(x,y): if x < N and y < M: return table[x][y] else: return table[N-1][M-1] # the max 

所以它的行为就像一个正方形没有占用更多的内存（在速度的代价，可能，取决于caching…哦，以及：P）

Answer 12

编辑：

我误解了这个问题。 正如评论指出的，这只适用于更受限制的情况。

在像C这样的一种语言中，按照行优先顺序存储数据，只要把它当作一个大小为n * m的一维数组，并使用二进制search。

Answer 13

我有一个recursion的分而治之解决scheme。 一步的基本思想是：我们知道左上（LU）是最小的，右下（RB）是最大的，所以给定的No（N）必须：N> = LU和N < RB

IF N == LU和N == RB ::::发现元素并中止返回位置/索引如果N> = LU且N <= RB = FALSE，否则不存在并中止。 如果N> = LU且N <= RB = TRUE，则将二维arrays按照逻辑方式分成二维​​arrays的四个相等部分。然后对所有四个子arrays应用相同的algorithm步骤。

我的algorithm是正确的我已经在我的朋友PC上实现。 复杂性：在最坏的情况下，每4个比较都可以用来推断出元素的总数为1/4。所以我的复杂度是1 + 4 x lg（n）+ 4但是真的预计这个在O （n）的

我认为在我的计算复杂性的某个地方是错误的，如果是的话请纠正。

Answer 14

最佳解决scheme是从左上angular开始，价值最低。 向右对angular地向右移动，直到您击中给定元素值>>的元素。 如果元素的值等于给定元素的值，则返回值为true。

否则，从这里我们可以以两种方式进行。

策略1：

1. 在列中向上移动，search给定的元素，直到达到最后。 如果find，返回发现为真
2. 在行中向左移动并search给定的元素，直到到达结尾。 如果find，返回发现为真
3. 返回发现为false

策略2：让我表示行索引，j表示我们停止的对angular元素的列索引。 （在这里，我们有我= j，BTW）。 令k = 1。

• 重复以下步骤直到ik> = 0
  1. search一个[ik] [j]是否等于给定的元素。 如果是，返回发现为真。
  2. search一个[i] [jk]是否等于给定的元素。 如果是，返回发现为真。
  3. 增加k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Answer 15

 public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){ // base case for recursion if(minX > maxX || minY > maxY) return false ; // early fails // array not properly intialized if(arr==null || arr.length==0) return false ; // arr[0][0]> key return false if(arr[minX][minY]>key) return false ; // arr[maxX][maxY]<key return false if(arr[maxX][maxY]<key) return false ; //int temp1 = minX ; //int temp2 = minY ; int midX = (minX+maxX)/2 ; //if(temp1==midX){midX+=1 ;} int midY = (minY+maxY)/2 ; //if(temp2==midY){midY+=1 ;} // arr[midX][midY] = key ? then value found if(arr[midX][midY] == key) return true ; // alas ! i have to keep looking // arr[midX][midY] < key ? search right quad and bottom matrix ; if(arr[midX][midY] < key){ if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY)) return true ; // search bottom half of matrix if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY)) return true ; } // arr[midX][midY] > key ? search left quad matrix ; else { return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1)); } return false ; } 

Answer 16

我build议将所有的字符存储在一个2D list 。 然后find所需元素的索引，如果它存在于列表中。

如果不存在，打印适当的消息，否则打印行和列为：

row = (index/total_columns)和column = (index%total_columns -1)

这只会导致列表中的二进制search时间。

请提出任何更正。 🙂

Answer 17

如果O（M log（N））解决scheme适用于MxNarrays –

 template <size_t n> struct MN * get(int a[][n], int k, int M, int N){ struct MN *result = new MN; result->m = -1; result->n = -1; /* Do a binary search on each row since rows (and columns too) are sorted. */ for(int i = 0; i < M; i++){ int lo = 0; int hi = N - 1; while(lo <= hi){ int mid = lo + (hi-lo)/2; if(k < a[i][mid]) hi = mid - 1; else if (k > a[i][mid]) lo = mid + 1; else{ result->m = i; result->n = mid; return result; } } } return result; } 

工作C ++演示。

请让我知道如果这不起作用，或者如果有一个错误它。

Answer 18

给定一个matrix如下：

 [abc]
 [def]
 [ijk]

我们知道a <c，d <f，i <k。 我们不知道的是d <c或d> c等，我们只有一维的保证。

看看最后的元素（c，f，k），我们可以做一个filter：是N <c？ search（）：next（）。 Thus, we have n iterations over the rows, with each row taking either O( log( n ) ) for binary search or O( 1 ) if filtered out.

Let me given an EXAMPLE where N = j,

1) Check row 1. j < c? (no, go next)

2) Check row 2. j < f? (yes, bin search gets nothing)

3) Check row 3. j < k? (yes, bin search finds it)

Try again with N = q,

1) Check row 1. q < c? (no, go next)

2) Check row 2. q < f? (no, go next)

3) Check row 3. q < k? (no, go next)

There is probably a better solution out there but this is easy to explain.. 🙂

Answer 19

As this is an interview question, it would seem to lead towards a discussion of Parallel programming and Map-reduce algorithms.

See http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html