二位数组中的查找

image.png

题目描述

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

首先试了下暴力法求解，没有问题。

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

eg:如果真的这样就太young太simple了，所以肯定有简单的方法，不然给这么多暗示干嘛

题目中说每一行从左到右递增，每一列从上到下递增，所以我们可以知道左上方最小，右下方最大。因此我们可以找一个支撑点，比如左下方或者右上方，以左下方为例，上面的比它小，右面的比它大。

function Find(target, array)
{
   let column = array.length;
   let row = array[0].length;
   let m = row-1;
   let n = 0;
    while(m>=0 && n<=column-1){
        if(array[n][m]>target){
            m--;
        }else if(array[n][m]<target){
            n++;
        }else{
            return true;
        }
    }
    return false;
}