如何在有规律的二维数组中进行高效的数据查找？

轩辕小不懂发布于 2022-03-28 11:45

阅读 659

答案 1

分类：人工智能

人工智能

python

编程论坛

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请实现一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

3379

Nen 2022-03-28 13:49

- 程序员

最简单的方法就是对二维数组进行顺序遍历，然后判断待查找元素是否在数组中，这种方法的时间复杂度为O(M×N)，其中，M、N分别为二维数组的行数和列数。

虽然上述方法能够解决问题，但这种方法显然没有用到二维数组中数组元素有序的特点，因此，该方法肯定不是最好的方法。

此时需要转换一种思路进行思考，在一般情况下，当数组中元素有序的时候，二分查找是一个很好的方法，对于本题而言，同样适用二分查找，实现思路如下。

给定数组array（行数：rows，列数：columns，待查找元素：data），首先，遍历数组右上角的元素（i=0，j=columns-1），如果array[i][j]==data，则在二维数组中找到了data，直接返回；如果array[i][j]＞data，则说明这一列其他的数字也一定大于data，因此，没有必要在这一列继续查找了，通过j-操作排除这一列。同理，如果array[i][j]＜data，则说明这一行中其他数字也一定比data小，因此，没有必要再遍历这一行了，可以通过i+操作排除这一行。依次类推，直到遍历完数组结束。