给定一个二维数组按从左到右和从上到下的顺序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 

这是一个简单的方法:

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

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


编辑:很多很好的讨论。 我在谈论上面的一般情况, 显然,如果NM很小,那么可以使用二分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了一对相邻的数字sg ,其中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变得越来越长。

这个问题需要Θ(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; } 

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

这将是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) } 

到目前为止,两个主要的答案似乎是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"); } } 

这是问题的下限的简短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函数可以得到改善。

我想这是答案,它适用于任何种类的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)); } } 

有趣的问题。 考虑这个想法 – 创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的计数额外的奖金。

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

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

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

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

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

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

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

 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.寻找一个矩形,天真的方法

当然,当NM不同(用一个矩形)时,它会变得更复杂,考虑这个退化的情况:

 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)

编辑:

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

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

我有一个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)的

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

最佳解决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

 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 ; } 

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

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

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

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

请提出任何更正。 🙂

如果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 ++演示。

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

给定一个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.. 🙂

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