JZ4 二维数组中的查找
难度：中等
描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
数据范围
数据范围：矩阵的长宽满足0≤n,m≤500,矩阵中的值满足 0≤val≤10^9
进阶：空间复杂度O(1),时间复杂度O(n+m)
举例
比如在下面的二维数组中查找数字7，查找过程如下：
解题思路
很明显，由于该二维数组上到下递增，左到右递增的特殊性，遍历整个矩阵进行查找不是该题目的意图所在。总结规律我们可以发现：应该从矩阵的右上角或者左下角开始查找。
以右上角为例，首先选取右上角的数字，如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则说明该列其他元素都大于要查找的数字，便可以删掉该列；如果该数字小于要查找的数字，则说明该行其他元素也都小于要查找的数字，便可以删掉该行。
这样，每一次比较都可以剔除一行或者一列，进而缩小查找范围，时间复杂度为O(n) 。
编程实现（java）
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { //如果数组为空，则直接返回false if(matrix==null || matrix.length == 0 ) { return false; } //从右上角开始找 int i=0,j=0; for(i =0,j=matrix[0].length-1; i=0;) { if(matrix[i][j] == target) { return true; //如果找到直接返回true } else if(matrix[i][j]>target) { //如果该值大于查找值，跳过该列 j--; } else { //如果该值小于查找值，跳过该行 i++; } } return false; //最后记得返回false，不然会报错 } }
结果
