1 二维数组的查找:
- 在一个二维数组中 ,每一行都按照从左到右递增的顺序排列,每一列都按照从上到下递增的顺序排列.
- 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
- 1 2 3 4
- 4 8 12 16
- 5 10 15 20
2 代码实现 :
public boolean search(int[][] array,int target){
int len = a.length-1;
int i=0;
while (len>=0&&i<a[0].length){
if(target>a[len][i]){
i++;
}else if(target<a[len][i]){
len--;
}else {
return true;
}
}
return false;
}
3 代码分析 :
因为二维数组是有序的，我们把数组看成M×N矩阵，从左到右，从上到下是依次递增的，所以我们从左下角开始循环，如果要查找的数大于左下角的数，就在右半部分的矩阵中查找（把第一列去掉，变成M×(N-1)的矩阵），因为第一列的最大的数都小于要查找的数。反之，如果要查找的数小于左下角的数，就在上半部分的矩阵中查找(把最后一行去掉，变成(M-1)×N的矩阵)。当遍历到第一行的时候还没有找到，那么就不存在。
