算法：寻找一个整数的二维整数数组有效的方法？ [英] Algorithm: efficient way to search an integer in a two dimensional integer array?

问题描述

可能显示的文件：
  <一href="http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom">Given二维数组排序从左至右，从上到下递增的顺序，什么是搜索目标数量的最佳方法是什么？
  搜索排序的二维矩阵

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

一个时间高效程序找出在二维矩阵的元素，行和列都在增加单调。 （行和列从由上而下增加和从左至右）。

A time efficient program to find an element in a two dimensional matrix, the rows and columns of which are increasing monotonically. (Rows and columns are increasing from top to bottom and from left to right).

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

I can only think of binary search, if the 2D array was sorted.

推荐答案

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

I posed this problem as homework last semester, and two students, which I had considered to be average, surprised me by coming up with a very elegant, straightforward, and (probably) optimal algorithm:

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）的算法执行。该解决方案比二分搜索分拆（该解决方案，我预计发放出这个问题时）更好。

This algorithm eliminates either one line or one column at every call (note that it is tail recursive, and could be transformed into a loop, thereby avoiding the recursive calls). Thus, if your matrix is n*m, the algorithm performs in O(n+m). This solution is better than the dichotomic search spin off (which the solution I expected when handing out this problem).

修改：我固定一个错字（K成为的X递归调用），还有如克里斯指出，这应首先被调用，使用右上一角，也就是查找（ K，选项卡，N，1），其中的 N 的是行数。

EDIT : I fixed a typo (k became x in the recursive calls) and also, as Chris pointed out, this should initially be called with the "upper right" corner, that is Find(k, tab, n, 1), where n is the number of lines.

这篇关于算法：寻找一个整数的二维整数数组有效的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！