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

Question

可能重复:
给定一个从左到右,从上到下按升序排序的二维数组,搜索目标数的最佳方法是什么？
搜索已排序的2D矩阵

一种时间有效的程序,用于在二维矩阵中查找元素,其行和列单调增加.(行和列从上到下,从左到右).

如果2D数组已经排序,我只能想到二分搜索.

Answer 1

我把这个问题作为上学期的家庭作业提出来了,我认为是平均的两个学生通过提出一个非常优雅,直截了当,(可能)最优的算法让我感到惊讶:

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),而且正如克里斯所指出的那样,最初应该用"右上角"调用,即Find(k,tab,n,1),其中n是行数.

Answer 2

由于行和列的单调增加,你可以像这样做一个简洁的小搜索:

从左下角开始.如果您要查找的元素大于该位置的元素,请向右移动.如果它少了上去.重复,直到找到元素或者你到达边缘.示例(以十六进制格式化,使格式更容易):

1 2 5 6 7
3 4 6 7 8
5 7 8 9 A
7 A C D E

让我们搜索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)平均和最差情况下运行.