二维数组中的查找

题目描述

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

思路

矩阵是有序的，如下矩阵：

let array = [
  [1, 2, 3, 4],
  [2, 3, 4, 5],
  [3, 4, 5, 6],
];

从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，

当要查找数字比左下角数字大时，右移；

要要查找数字比左下角数字小时，上移；

或者，

从右上角来看，向下数字递增，向左数字递减，因此从右上角开始查找，

当要查找数字比右上角数字大时，下移；

要要查找数字比右上角数字小时，左移；

代码

从左下角来看：

function Find(target, array) {
  // 首先取出二维矩阵的行列数
  let row = array.length; // 行数
  let col = array[0].length; // 列数

  let i = row - 1,
    j = 0; // 取出左下角数的下标

  while (i >= 0 && j < col) {
    let value = array[i][j];
    if (value === target) {
      return true;
    } else if (target < value) {
      i--; // 要要查找数字比左下角数字小时，上移，行坐标减1；
    } else {
      j++; // 当要查找数字比左下角数字大时，右移，列坐标加1；
    }
  }
  return false;
}

从右上角来看：

function Find(target, array) {
  // 首先取出二维矩阵的行列数
  let row = array.length; // 行数
  let col = array[0].length; // 列数

  let i = 0,
    j = col - 1; // 取出右上角的数的下标

  while (i < row && j >= 0) {
    let value = array[i][j];
    if (value === target) {
      return true;
    } else if (target < value) {
      j--; // 要要查找数字比右上角数字小时，左移，列坐标减1；
    } else {
      i++; // 当要查找数字比右上角数字大时，下移，行坐标加1；
    }
  }
  return false;
}