剑指Offer之二维数组中查找目标数
题目描述
在一个二维数组中（每个一维数组的长度相等），每一行都是从左到右递增的顺序排序，每一列都是从上到下递增的顺序排序，输入这样一个二维数组和一个整数，判断该整数是否在二维数组中。
解题思路及代码
// 暴力查找法，通过遍历整个二维数组进行判断
public static boolean violence(int[][] arr,int target) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++){
if (arr[i][j] == target)
return true;
}
}
return false;
}
/**
* tips: 二维数组其实就是元素类型为数组的一维数组。 ex: {{1，2，3}，{2，3，4}，{3，4，5}}
* 可理解为： 1，2，3
* 2，3，4
* 3，4，5
* 此时我们可以将target 和每一行的最后一个元素作比较，有三种情况发生
* 1. 相等 则直接返回true 即二维数组中存在该元素
* 2. 最后一个元素 > target 则target不可能存在当前行中，直接跳转到下一行
* 3. 最后一个元素 < target 则每个一维数组的最后一行都不用比较了
*
*/
public static boolean find(int[][] array,int target) {
int maxX = array.length;
int maxY = array[0].length;
int x = 0;
int y = maxY - 1;
while (x < maxX && y >= 0) {
if (array[x][y] == target)
return true;
if (array[x][y] > target)
y--;
else
x++;
}
return false;
}