Kotlin程序员高效数据查找算法

【出自TX面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

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

例如下面的二维数组就是符合这种约束条件的。如果在这个数组中查找数字7，由于数组中含有该数字，则返回true；如果在这个数组中查找数字5，由于数组中不含有该数字，则返回false。

1

分析与解答：

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

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

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

给定数组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++操作排除这一行。依次类推，直到遍历完数组结束。

实现代码如下：

程序的运行结果如下：

false

true

算法性能分析：

这种方法主要从二维数组的右上角遍历到左下角，因此，算法的时间复杂度为O（M+N），此外，这种方法没有申请额外的存储空间。