题目描述

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

function Find(target, array){

    //思路一：遍历，暴力搜索。
　　 /*
       var row = array.length;
       var col = array[0].length;
       for(var i=0;i<col;i++){
          for(var j=0;j<row;j++){
              if(array[i][j]==target){
                  return true;
              }
          }
      }
      return false;
    */
    
    //思路二：利用题目已知条件，矩阵是有序的。从右上角开始，不断剔除列和行，直至找到target。
    var res=false;//定义返回结果为false
    var row = array.length;
    var col = array[0].length;
    if(array!=null&&row>0&&col>0){
        var i=0;
        var j=col-1;//i、j表示从数组的右上角开始比较
        while(i<row&&j>=0){//终止条件
            if(array[i][j]==target){
                res=true;//找到target，返回结果为true，终止程序
                break;
            }else if(array[i][j]>target){
                j--;// 如果元素比目标数大，说明元素所在的列的值都不可能，列左移
            }else{
                i++;// 如果元素比目标数小，此时的元素所在的行的值都不可能，行下移
            }         
        }
    }
    return res;
}