[74] 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

从矩阵特性的描述中，我们很容易看出，矩阵就是用一个升序数组从左至右一行一行排列而来的。

那么，问题显然就变成了在有序数组中寻找目标值的问题。直接考虑使用经典二分查找来解。

function searchMatrix(matrix: number[][], target: number): boolean {
  const flattedArr = matrix.reduce((arr1, arr2) => [...arr1, ...arr2]);

  let left = 0;
  let right = flattedArr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (flattedArr[mid] === target) {
      return true;
    } else if (flattedArr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
}

当然，如果题目有要求不使用额外空间的话，我们就得考虑仅用二维数组来解题了。

实际上，二分查找的思路是没有变的，需要做出改变的仅有数组的取值方式，利用整除和取模的方式将一维的坐标转为二维即可。

function searchMatrix(matrix: number[][], target: number): boolean {
  const height = matrix.length;
  const width = matrix[0].length;

  let left = 0;
  let right = height * width - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midElement = matrix[Math.floor(mid / width)][mid % width];
    if (midElement === target) {
      return true;
    } else if (midElement < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
}