4 二维数组中的查找

牛客

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

[ [1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15] ]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

---

如果一行一行遍历，时间复杂度为 O(n₂)。快捷的方法是从右上角或左下角开始，如果值比 target 大，说明 target 在左边，比 target 小说明在下边，如果超出边界，说明不存在。时间复杂度为 O(n)，空间复杂度为 O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null || array.length==0 || array[0].length==0)
            return false;
        int i=0,j=array[0].length-1;
        int t;
        while(i<array.length && j>=0){
            t=array[i][j];
            if(t>target){
                --j;
            }else if(t<target){
                ++i;
            }else{
                return true;
            }
        }
        return false;
    }
}