题解 | #二维数组中的查找#

描述：在一个二维数组array中（每个一维数组的长度相同），

1. 每一行都按照从左到右递增的顺序排序，
2. 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：不断地收缩矩阵的边界。

具体方法：

定义四个变量代表范围，up、down、left、right.先遍历上边界，遇到比target值大的元素，right更新为当前元素的前一列。当前行遍历结束，上边界加1，即up++；再遍历左边界，遇到比target值大的元素，down更新为当前元素的上一行，当前列遍历结束，左边界加1，即left++.

复杂度分析：

平均时间复杂度O(m+n),空间复杂度O(1)

public class Solution {
	public boolean Find(int target, int [][] array) {
		if (array.length==0||array[0].length==0) return false;
		int up=0,left=0;//up上边界，left左边界
        int down=array.length-1;//下边界
        int right=array[0].length-1;//右边界
        //若target比左上角元素小或者target比右下角元素大，一定找不到
        if(target<array[0][0]||target>array[down][right]) return false;
        while(true) {
        	 for(int col=left;col<=right;col++) {//遍历上边界
             	if(array[up][col]==target) return true;
             	if(array[up][col]>target) {
             		right=col-1;//右边界向左收缩
             		break;
             	}
             }
        	 up++;//上边界遍历结束，上边界向下收缩
        	 if(left>right||up>down) return false;
             for(int row=up;row<=down;row++) {//遍历左边界
             	if(array[row][left]==target) return true;
             	if(array[row][left]>target) {
             		down--;//下边界向上收缩
             		break;
             	}
             }
             left++;//左边界遍历结束，左边界向右收缩
             if(left>right||up>down) return false;
        }
       
        
    }
}