深色模式
BM18 二维数组中的查找
描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
ts
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0 \le val \le 10^90≤val≤109进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)
示例1
输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
说明：存在7，返回true
示例2
输入：1,[[2]]
返回值：false
示例3
输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
说明不存在3，返回false
1. 每行二分查找
ts
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param target int整型
* @param array int整型二维数组
* @return bool布尔型
*/
export function Find(target: number, array: number[][]): boolean {
// write code here
function binarysearch(array: number[], start, end, target) {
if(start > end) return false;
var mid = Math.floor((start + end) /2);
if(array[mid] === target) return true;
if(array[mid] < target) return binarysearch(array, mid+1, end, target);
return binarysearch(array, start, mid-1, target)
}
for(var i = 0; i < array.length; i++) {
var res = binarysearch(array[i], 0, array[i].length -1, target)
if(res) return true;
}
return false;
}2. 线性搜索
解题思路：
利用二维数组行列递增特性主要思路：
- 由于行列递增，可以得出：a.在一列中的某个数字，其上的数字都比它小b.在一行中的某个数字，其右的数字都比它大
- 搜索流程：a.首先从数组左下角搜索.b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。c.查找到target,返回true; 如果越界，返回false;
示例如下： 
复杂度分析:
时间复杂度: O(M+N)
空间复杂度: O(1)
ts
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param target int整型
* @param array int整型二维数组
* @return bool布尔型
*/
export function Find(target: number, array: number[][]): boolean {
// write code here
let maxrow = array.length;
let maxcol = array[0].length;
let m = maxrow -1; // 行
let n = 0; // 列
while(m >= 0 && n < maxcol) {
let tmp = array[m][n];
if(tmp === target) return true;
if(tmp < target) {
n++;
} else {
m--;
}
}
return false;
}