面试题4: 二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
方法一 暴力解法，循环两层数组 时间复杂度： O(n^2)
//方法1：遍历，这是最简单的最暴力的方法了
public boolean find(int target, int [][] array) {
int xlen = array[0].length;
int ylen = array.length;
for (int i = 0; i < ylen; i++) {
for (int j = 0; j < xlen; j++) {
if (array[i][j] == target) return true;
}
}
return false;
}
方法二
时间复杂度：最多就是遍历完行，遍历完列最后查找到或没找到，就是行与列的和，也就是： O(n)
//思路2：选取右上角的一点进行查询，如果所选数比目标数大，则不在所选数的列，小，不在所选数的行
// 一步步的缩小范围
public boolean find_2(int target, int [][] array) {
int xlen = array[0].length;
int ylen = array.length;
for (int x = xlen-1,y = 0; x >= 0 && y < ylen; ) {
if (array[y][x] > target)
x--;
else if (array[y][x] < target)
y++;
else return true;
}
return false;
}