题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入输出分析
每当拿到一个算法题的时候，不要脑子中稍微有点思路后，就开始写代码。而是先把题目中规定的参数搞清楚，然后把参数的例子写出来。
本题两个参数举例：
- 递增二维数组
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
注意 题目只说每一行是递增的，没有说增幅是多少，不要以为增幅是1。同时也没有说行数和列数相等
- 要查找的整数
比如：7、5、0、16
对应的输出结果：true、false、false、false
实现思路
- 暴力遍历法
面试官要的肯定不是这个结果，直接跳过
- 二分查找法
仔细看这个二维数组最右上角这个数。它所在的行，左面的数字比它小；所在的列，下面的数字比它大：
在这里插入图片描述
如果要查询的数字比9大，那么9所在的行就不用在比较了，接下来只需要比较9下面的所有行
在这里插入图片描述
如果要查询的数字比9小，那么9所在的列就不用在比较了，接下来只需要比较9左面的所有列
在这里插入图片描述
通过这一次的比较，我们就能得到一个新的范围（矩形）。接着继续利用新范围右上角的数字，与要查找的整数进行比较。比较过后，又能得到一个新的进一步缩小的范围（矩形）。如此往复，直到找到目标整数，或者没有找到。
每一次比较的过程，比较类似二分查找
比如要查找数字7，那么查找的路径如下图：
在这里插入图片描述
每一步都是通过比较所在行左面数字和所在列下面数字的大小，确定下一步指针的移动方向。
同理，我们还可以从矩形的左下角的数字开始比较
最后，别忘了要把特殊情况考虑进去，比如参数的特殊值
代码实现
function find(target, array) {
let rows = 0; // 右上角数字所在的行
let cols = array[0].length - 1; // 右上角数字所在的列
let result = false;
// 特殊情况判断. 其他特殊情况比如target不在array里,这里不在列举
if(array.length === 0) return false;
while(cols >= 0 && rows < array.length) {
if(array[rows][cols] === target) {
result = true;
break;
} else if(array[rows][cols] > target) {
// 如果右上角数字比目标数字大,向左移动指针
cols--;
} else {
// 如果右上角数字比目标数字小,向下移动指针
rows++;
}
}
return result;
}
