题解 | #18.二维数组中的查找#

题解是抄的，为了我之后更方便找而已

题目所提供的矩阵，是一种特殊的矩阵，称作杨氏矩阵，其有特定的查找算法，时间复杂度 m,n分别为矩阵的两个维度。查找算法步骤如下：

1.从矩阵的左下角或者矩阵的右上角处开始递归运行，以左下角为例，value为要查找的值，(i,j)为当前矩阵中的位置，初始为(M-1, 0)

2.如果超过了矩阵范围则说明不存在这样的元素，返回false

3.否则的话，如果当前位置的值大于value，说明要移动位置(向上移一行)，使得数值减小，即递归使得i=i-1；如果当前位置的值小于value，说明要移动位置(向右移一列)，使得数值增大，即递归使得j=j+1；如果刚好等于value，返回当前的位置true即可

查找过程如红色箭头所示：

我们在6的位置，发现6比12小，那么6上面的数比6小，右边的数比6大，那么只能向右边走

同理在8，11，一样

当移动到了15，15比12大，那么12一定在15的上方，向上移动

同理在13一样，最后在12处找到了目标值。

function Find(target, array)
{
  //判断数组是否为空
  let m = array.length;
  if(m == 0)  return false;
  
  let n = array[0].length;
  if(n == 0)  return false;
  
  let i=0, j=n-1;//右上角元素
  while(i<m && j>=0){
    if(target < array[i][j]){
      j--;
    }else if(target > array[i][j]){
      i++;
    }else{
      return true;
    }
  }
  return false;
}
module.exports = {
    Find : Find
};