题目描述

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

例如：

输入：16, [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
输出：false

一般情况下我们可以使用两个for循环进行遍历，代码是这样：

function Find(target, array){
    for(var i = 0;i < array.length;i++){
        for(var j = 0;j < array[i].length;j++){
            if(array[i][j] == target){
                return true;
            }
        }
    }
    return false;
}

但是这样浪费了题目中的信息，题目中说这是一个有序序列，并且子数组的长度相同，并且这样的时间复杂度是O(n^2)。

所以可以考虑其它方式，首先把数组写成二维的样式，如下：

观察得知从上至下是递增，从左至右也是递增。现在以左下角的数字9作为开始数字，对传入的数字与9相比较，如果比9小则向上移动，如果比9大则向右移动，一直重复就可以找到这个数字。
为什么不从左上角开始呢，因为左上角不管向下还是向右都是递增，这是一个分岔路口，程序不知道应该走哪边，所以选择左下角唯一的。
代码如下：

function Find(target, array) {
    var num1 = array.length;
    var num2 = array[0].length;
    for (var i = 0, j = num2 - 1; i < num1 && j >= 0;) {
        /*
            i代表列，j代表行，初始就为左下角的数字。
            i<num1是列的边界，j>=0是行的边界（子数组边界）
        */
        if (target == array[i][j]) {
            return true;
        }
        if (target > array[i][j]) {
            i++;
            continue;
        }
        if (target < array[i][j]) {
            j--;
            continue;
        }
    }
    return false;
}

当然也有一些其它方法，比如把子数组进行二分法查找，并对每个子数组都这样操作。不过这里就讨论了。