面试题3：二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。
这个问题本身是很简单的，书中提供一个很好的思路 -- 找规律。一会儿我们详细探讨 这个算法思想。下面感受一下它的解法有哪些？
暴力
时间复杂度为O(mn)
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) return false;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if (target == array[i][j]) {
return true;
}
}
}
return false;
}
这是一个非常传统的思路，也是一个易于实现、适合新手的方案。
找规律
规律一
这个规律其实也算不上规律吧，基本上就是题干的描述 -- 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
书上说：在分析这个问题的时候，很多应聘者都会把二维数组画成矩形，然后从数组中选取一个数字，分3种情况来分析查找的过程。当数组中选取的数字刚好和要查找的数字相等时，就结束查找过程。如果选取的数字小于要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前选取的位置的右边或者下边（如图2.1（a）所示）。同样，如果选取的数字大于要查找的数字，那么要查找的数字应该在当前选取的位置的上边或者左边（如图2.1（b）所示）。
在上面的分析中，由于要查找的数字相对于当前选取的位置有可能在两个区域中出现，而且这两个区域还有重叠，这问题看起来就复杂了，于是很多人就卡在这里束手无策了。
这里有解法吗？ 当然有。 不过实现需要借助二分查找算法。
每一行都按照从左到右递增的顺序排序，把每一行看作有序递增数组，利用二分查找，通过遍历每一行查找得到答案，时间复杂度mlog(n)
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) return false;
for (int i = 0; i < array.length; i++) {
int begin = 0;
int end = array[0].length - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (target > array[i][mid]) {
begin = mid + 1;
} else if (target < array[i][mid]) {
end = mid - 1;
} else {
return true;
}
}
}
return false;
}
这样子的话，也遵循了思路。与遍历相比也有一定的优化。
如果非要完完全全的按照 下面的思路走，那实现起来可就非常折腾了。
-
如果选取的数字小于要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前选取的位置的右边或者下边
-
如果选取的数字大于要查找的数字，那么要查找的数字应该在当前选取的位置的上边或者左边
二维数组本身具有非常强的规律性，尤其是矩阵型的，直接有一门相关的数学 -- 线性代数 对其进行了非常详尽、深入的探讨。
对于这种规律非常强的数学模型（场景不局限于二维数组），在动手写代码之前一定要好好想想，用笔画画，有没有更好的规律可以为我们所用。想想小学数学课的找规律（又不要求你证明，难度没那么高）。
当你通过刷题，见识了这些常见的数学模型各种各样的场景，并能够熟练把握其内在规律，很多东西对你来说思考代价会非常低。比如说矩阵型的二维数组可以拓展成棋盘等等，一些数学问题，换种说法，总不能一问三不知吧。
规律二
这是书上的解法的算法思想，效率比较高。
利用二维数组由上到下，由左到右递增的规律，那么选取左下角或者右上角的元素a[i][j]与target进行比较.
当target大于元素a[i][j]时，那么target必定在元素a所在行的右边, 即j++；
当target大于元素a[i][j]时，那么target必定在元素a所在列的上边,即i- -；
时间复杂度为O(m+n)
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) return false;
int i = array.length - 1;
int j = 0;
while (i >= 0 && j <= array[0].length) {
if (target > array[i][j]) {
j++;
} else if (target < array[i][j]) {
i--;
} else {
return true;
}
}
return false;
}
我们通过练习，能够见识到很多的数学模型。在这些数学模型中有很多是规律非常强的，通过对它们的规律的把握与分析，能提供给我们非常好的问题解决方案。
这道题并不难，但是我想传达给你的，你Get到了吗？