算法题8.二维数组中的查找

题目描述:

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

乍一看题目有点小懵，不过再慢慢读一遍便理解了，如下面找个数组就是满足要求的一个数组：

1 2 3
2 5 8
5 6 9

数组每一行都是递增的，每一列都是递增的。

题是读懂了，但是一时没想到有什么好的办法，那就先暴力破解：

public class Solution {

    public boolean Find(int target, int[][] array) {
        for (int[] row : array) {
            for (int num : row) {
                if (target == num) {
                    return true;
                }
            }
        }
        return false;
    }
}

通过，然后再想想优化的事情：内层循环每次遍历的其实是一个递增的序列，所以可以采用二分查找来优化效率。但是很神奇的是用了二分反而会报错说是循环过多，真是玄学（当然可能是我的二分写的太low了）。。

参考答案：
这是评论区获赞最高的一种解法，其思路就是将二维数组看成一个矩阵，然后从左下角看是查找，当要查找数字比左下角数字大时。右移；要查找数字比左下角数字小时，上移。

/* 思路：
 * 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
 * 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
 * 要查找数字比左下角数字小时，上移
 */
public boolean Find(int target, int[][] array) {
    int line = array[0].length;  //列数
    int i = 0, j = line - 1;  //左下角那个数的下标位置

    //开始查找
    while (i < line && j >= 0) {
        if (target == array[i][j]) {
            return true;
        }

        //如果target比该数大，则向右移（i++），否则向上移（j--）
        if (target > array[i][j]) {
            i++;
        } else {
            j--;
        }
    }

    return false;
}

实测可以成功通过，不过恕我愚钝，还是不太能理解为什么可以这样 = = 。