标签 algorithm
<分区>
Possible Duplicates:
Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?
Search a sorted 2D matrix
一个高效的程序，用于查找二维矩阵中的元素，其行和列单调递增。 (行和列从上到下和从左到右递增)。
如果二维数组已排序，我只能想到二进制搜索。
最佳答案
我把这个问题作为上学期的家庭作业，两个我认为一般的学生提出了一个非常优雅、直接且(可能)最优的算法，这让我感到惊讶:
Find(k, tab, x, y)
let m = tab[x][y]
if k = m then return "Found"
else if k > m then
return Find(k, tab, x, y + 1)
else
return Find(k, tab, x - 1, y)
该算法在每次调用时去掉一行或一列(注意它是尾递归的，可以转化为循环，从而避免递归调用)。因此，如果您的矩阵是 n*m，则该算法的执行时间为 O(n+m)。这个解决方案比二分搜索分拆更好(这是我在提出这个问题时所期望的解决方案)。
编辑:我修正了一个拼写错误(k 在递归调用中变成了 x)，而且正如 Chris 指出的那样，这最初应该用“右上”角调用，即 Find( k, tab, n, 1), n 是行数。
关于算法:在二维整数数组中搜索整数的有效方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3477442/