剑指offer之二维数组的查找
题目描述
在一个二维数组中(每个一维数组的长度相同)，
每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
要求时间复杂度O(M+N)，空间复杂度O(1)。
该二维数组中的一个数，它左边的数都比它小，下边的数都比它大。
因此，从右上角开始查找，就可以根据target和当前袁旭的大小关系来缩小查找区间，
当前元素的查找区间为左下角的所有元素。
解题代码
public static void main(String[] args) {
int[][] matrix = {
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22}
};
System.out.println(find(30, matrix));
}
public static boolean find(int target, int[][] matrix) {
if (matrix == null || matrix.length <= 0) {
return false;
}
int rows = matrix.length, cols = matrix[0].length;
int r = 0, c = cols - 1;
while (r <= rows - 1 && c >= 0) {
System.out.println("matrix[" + r + "][" + c + "]=" + matrix[r][c]);
if (target == matrix[r][c]) {
return true;
} else if (target > matrix[r][c]) {
r++;
} else {
c--;
}
}
return false;
}