一、题目描述
一个二维数组，满足：每一行数字大小从左至右递增，每一列从上至下递增。求：一个函数，其满足输入一个二维数组与一个整数，判断数组是否含有该整数。
二、解决方法
- 1、最直接了当的方法
function find(target, arr)
{
let len=arr.length;
for(let i=0;i<len;i++){
for(let j=0;j<arr[i].length;j++){
if(arr[i][j]==target)return true;
}
}
return false;
}
缺点：时间复杂度为o(n2)，根据题设条件可以再优化
- 2、采用二分法
function find(target,arr){
for(let i=0;i<arr.length;i++){
let low=0;
let high=arr[i].length-1;
while(low<=high){
let mid=Math.round((high+low)/2);
if(target<arr[i][mid])
high=mid-1;
else if (target>arr[i][mid])
low=mid+1;
else return true
}
}
return false;
}
优点：时间复杂度o(nlog2n)，但比第一种方法稍复杂
- 3、根据题设采用边界判断方法
function find(target,arr){
let m=arr.length;//行数
let n=arr[0].length//列数
let x=0;
let y=m-1;//从最左下角树开始
while(x<=n-1&&y>=0){//只要在边界内
if (target<arr[y][x])
y--;//上移
else if (target>arr[y][x])
x++;//右移
else return true
}
return false;
}
优点：完整结合了题设条件，是较切合的解决方法
三、评论
查找效率一直是算法优化的重点问题，不同的算法，带来的消耗是不同的，要达到快准狠，是需要一番研究与实验的。
