在一个二维数组中(每个一维数组的长度相同) ,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

    请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

    解题提示:二维数组是有序的,比如下面的数据:

    1 2 3
    4 5 6
    7 8 9

    可以直接利用左下角数字开始查找:
    大于: 比较上移
    小于: 比较右移
    解题思路:
    将二维数组看作平面坐标系从左下角(0, arr. Length-1)开始比较:
    目标值大于坐标值 -x 坐标+1
    目标值小于坐标值 -y 坐标-1
    注意:二维数组 arr[i][j] 中j代表x坐标,i代表y坐标

    更优方法:二分查找
    二分查找的条件是必须有序。和线性表的中点值进行比较
    如果小就继续在小的序列中查找,如此递归直到找到相同的值。

    1. // m*n 的矩阵
    2. // 按照对角线  二分查找
    3. var searchMatrix = function(array,target){
    4.   let i = array.length -1; // Y坐标
    5.   let j = 0; // X 坐标
    6.   return compare(target,array, i, j);
    7. }
    9. function compare(target,array,i,j){
    10.   if(array[i] === undefined || array[i][j] === undefined){
    11.     return false;
    12.   }
    13.   const temp = array[i][j];
    14.   if(target === temp){
    15.     return true;
    16.   } else if(target> temp){
    17.     return compare(target,array, i, j+1)
    18.   } else if(target< temp){
    19.     return compare(target,array,i-1,j)
    20.   }
    21. }
    24. // 二分法 横向查找数组
    25. function binarySearch(data, arr, start, end){
    26.     if (start > end) {
    27.     return -1
    28.   };
    29.   var mid =Math.floor((end + start) / 2);
    30.   if (data == arr[mid]) {
    31.     return mid;
    32.   } else if (data < arr[mid]) {
    33.       return binarySearch(data, arr, start, mid - 1);
    34.   } else {
    35.     return binarySearch(data, arr, mid + 1, end);
    36.   }
    37. }