在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
语言Java
方法一：
1.遍历每一行
2.对每一行进行二分法查找
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i = 0;i<array.length;i++){
int low = 0;
int high = array[i].length-1;
while(low<=high)
{
int mid = (low+high)/2;
if(target>array[i][mid])
low = mid+1;
else if (target<array[i][mid])
high = mid-1;
else
return true;
}
}
return false;
}
}
注意：二分法while的循环调节必须是带有等号、否则会少遍历最后一个数；
方法二：
1.从数组的左下那数开始（右上也可、左上和右下不可以）与目标数进行比较
2.如果大于目标数则在该数的左边、如果小于这个数则在该数的上边
public class Solution {
public boolean Find(int target, int [][] array) {
int x = array.length - 1;
int y = 0;
while(x>=0&&y<array[x].length)
{
if(target==array[x][y]){
return true;
}else if(target >array[x][y])
y ++;
else
x --;
}
return false;
}
}
错误方法
1.对列二分法
2.对行二分法
public class Solution {
public boolean Find(int target, int [][] array) {
int low = 0;
int high = array.length-1;
while(low<=high)
{
int mid = (low+high)/2;
if(target>array[mid][0])
low = mid + 1;
else if(target<array[mid][0])
high = mid - 1;
else
return true;
}
int rowlow = 0;
int rowhigh = array[high].length-1;
while(rowlow<=rowhigh)
{
int mid = (rowlow+rowhigh)/2;
if(target>array[high][mid])
rowlow = mid + 1;
else if(target<array[high][mid])
rowhigh = mid - 1;
else
return true;
}
return false;
}
}
这个方法不能通过的原因如下
测试用例:
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
对应输出应该为:
true
你的输出为:
false
