二维数组中的查找

题目：

题目

思路：

初次：整数先跟第一列的所有数比较，在和可能存在该数的那行进行比较。
初次结果：失败！

没考虑到的情况
显然，每一行的第一个数字的确是该行最小的，但是并不代表它比它上一行的所有数字都大。
第二次：考虑整数每次跟每行的头和尾进行两次比较，在这个区间，就遍历这一行，看能不能找到。
第二次结果：成功！

解答：

public class Solution {
    public boolean Find(int target, int [][] array) {
//判断数组为空的情况一定要考虑全面。
       if(array == null || array.length ==0 || array[0].length ==0) return false;
        int hanglen = array[0].length;
        int len = array.length;
        if (target > array[len - 1][hanglen - 1]) {
            return false;
        }
        if(target<array[0][0]) return false;
        if(target == array[0][0]) return true;
        int[] tou = new int[len];
        int[] wei = new int[len];
        for(int i=0;i<len;i++){
            tou[i] = array[i][0];
            wei[i] = array[i][hanglen-1];
            if(tou[i] == target || wei[i]==target) return true;
            if(tou[i]<target && wei[i]>target){
                for(int j =0;j<hanglen;j++){
                    if(array[i][j]==target){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

优化：

显然，如上方法用到两层for循环，并不是最佳的解法。
去看了大神的解法，考虑从右上角开始比较，因为在这个二维数组中的所有数字，都比左边的大，比下边的小。右上角是第一行的最大数字，如果比它小，则往左遍历比较，如果比它大，则行数+1往下遍历比较。
即：比它小则遍历比较这一行，比它大则跳过这一行，这样的比较次数能得到有效的减少。
思考，可不可以用左上角的数字来比较？左上角是第一行的最小值，比它小则返回false，比它大则遍历比较这一行？实践证明，不行！因为比左上角小用一行的最小值比较没有丝毫价值，不能较少比较的次数。
用右上角的值进行比较的解法如下：

public boolean Find(int target, int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int m = matrix.length, n = matrix[0].length;
    int r = 0, c = n - 1; // 从右上角开始
    while (r <= m - 1 && c >= 0) {
        if (target == matrix[r][c]) return true;
        else if (target > matrix[r][c]) r++;
        else c--;
    }
    return false;
}