算法：搜索二维整数数组中的整数的有效方法？

可能显示的文件：
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 算法：搜索二维整数数组中的整数的有效方法？

甲时间效率的程序，找出在二维矩阵的元素，行和列，其中的单调递增。（行和列从上到下和从左到右增加）。

我只能想到二进制搜索，如果二维数组排序。

来源

2010-08-13 Abhijeet

即使单调增加而不是排序，也可以进行二进制搜索，但正如指出的那样，有更好的方法可以继续。 – 2010-08-13 14:03:46

我提出这个问题，因为功课上学期，和两个学生，我曾认为是平均，通过想出一个非常优雅的，简单的，（可能）优化算法出乎我的意料：

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是行数。

来源

2010-08-13 13:59:59

以秒击败我！顺便说一下，Find的第二次递归调用需要大写。 – 2010-08-13 14:03:26

什么是z？这应该是米吗？ – Chris 2010-08-13 14:04:03

@Chris：是的，“z”应该再次“m”，我正是在阅读时纠正了这一点。 @Niki：哈哈哈，你只是想让我编辑我的帖子，所以时间戳会发生变化，看起来好像我在读完你的内容后修改了我的答案:-D – 2010-08-13 14:05:20

假设我读得对，你说第n行的底部总是小于第n + 1行的顶部。如果是这种情况，那么我会说最简单的方法是搜索第一行使用二进制搜索的数字或下一个最小的数字。然后，您将识别出所在的列。然后对该列进行二进制搜索，直至找到它。

来源

2010-08-13 14:00:48 Chris

由于行和列单调递增的，你可以这样做一个整洁的小搜索：

开始在左下角。如果您正在查找的元素大于该位置的元素，则向右。如果不那么上去。重复，直到找到该元素或您碰到一个边缘。示例（十六进制进行格式化更容易）：

让我们寻找8.开始在位置（0,3）：7 8> 7，所以我们去的权利。我们现在在（1，3）：A。8 < A，所以我们走了。在（1，2）：7，8> 7，所以我们走对了。（2,2）：8 - > 8 == 8所以我们完成了。

你会发现然而，这仅发现其价值的要素之一是8

编辑，万一这一点不明确这个运行在O（N + M）平均和最差案件时间。

来源

2010-08-13 14:00:59

开始在（0,0）

而值太低，继续向右侧（0,1），然后（0,2）等。
达到值过高时，下去一个，左一个（1,1）

重复这些步骤应该把你的目标。

来源

2010-08-13 14:02:47

这不起作用。（0,0）：1>（1,0）：2>（2,0）：5 v（1，1）：4 v（ 0，2）：5，下一步移动会带你离开边缘（我认为这将是“未找到”的条件）。 – 2010-08-13 14:17:42

算法：搜索二维整数数组中的整数的有效方法？

回答

相关问题