一、暴力解法:
分析:直接循环遍历二维数组,当找到目标值返回true,否则返回false。 实现:
public class Solution {
public boolean Find(int target, int [][] array) {
//判断数组是否为空,如果为空,直接返回false
if(array.length == 0 || array[0].length == 0){
return false;
}
for(int i=0;i<array.length;i++){
for(int j=0;j<array[0].length;j++){
if(target==array[i][j]){
return true;
}
}
}
return false;
}
}
二、二分查找法
分析:由题目可知,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。很显然这是一个有序的数组,所以我们可以使用二分查找法,我们可以选用二维数组四个角的数作为中间值,这里用左下角为例。 用目标值和中间值比较,如果目标值大于中间值,说明目标值在更大的区域,则向右移动;如果目标值小于中间值,说明目标值在更小的区域,则向上移动。 实现:
public class Solution {
public boolean Find(int target, int [][] array) {
//判断数组是否为空,如果为空,直接返回false
if(array.length == 0 || array[0].length == 0){
return false;
}
//从左下角为初始值和目标值作比较
int rows=array.length-1;//行
int colums=0;//列
int m;//比较值
while(rows>=0 && colums <array[0].length){
m=array[rows][colums];
if(target==m){
return true;//找到了
}else if(target > m){
//目标值大于比较值,则往右移动
colums++;
}else{
//目标值小于比较值,则往上移动
rows--;
}
}
return false;//没找到
}
}