二维数组中的查找

题目描述：
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
0 <= array.length <= 500
0 <= array[0].length <= 500

java code
法1；暴力法
暴力法很简单遍历二维数组因此时间复杂度是O(n^2)
空间复杂度O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {    
        //暴力法
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[i].length;j++){
                if(target==array[i][j])
                    return true;
            }
        }
        return false;
    }
}

但是暴力法没有利用题目给出的信息
法2：题目中的数组有顺序信息，由此想到有序数组的二分法查找，但这里是二维数组可以从右上角或者左下角出发，然后与target比较，改变i和j的值。这里注意判断条件：要使i和j在数组的范围内。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int n=array[0].length;
        int j=n-1;
        int i=0; 
        //int val=array[i][j];//从右上角开始,一直向下走，注意while里的内容
        while(i<n&&j>=0)//因为行是增加的所以i<n,而列是减少的所以j>=0
        {
             if(target<array[i][j])

                   j--;  //因为当前val正下一行值肯定比target大，因此要向左走，

        else if(target>array[i][j])
                 i++;
        else
           return true;  
        }
     return false;        
}