在一个二维数组中(每个一维数组的长度相同) ,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解题提示:二维数组是有序的,比如下面的数据:
1 2 3
4 5 6
7 8 9
可以直接利用左下角数字开始查找:
大于: 比较上移
小于: 比较右移
解题思路:
将二维数组看作平面坐标系从左下角(0, arr. Length-1)开始比较:
目标值大于坐标值 -x 坐标+1
目标值小于坐标值 -y 坐标-1
注意:二维数组 arr[i][j] 中j代表x坐标,i代表y坐标
更优方法:二分查找
二分查找的条件是必须有序。和线性表的中点值进行比较
如果小就继续在小的序列中查找,如此递归直到找到相同的值。
// m*n 的矩阵
// 按照对角线 二分查找
var searchMatrix = function(array,target){
let i = array.length -1; // Y坐标
let j = 0; // X 坐标
return compare(target,array, i, j);
}
function compare(target,array,i,j){
if(array[i] === undefined || array[i][j] === undefined){
return false;
}
const temp = array[i][j];
if(target === temp){
return true;
} else if(target> temp){
return compare(target,array, i, j+1)
} else if(target< temp){
return compare(target,array,i-1,j)
}
}