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

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

思路

  1. 二分查找 i = Math.floor(index / n), j = index % n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var searchMatrix = function (matrix, target) {
  const [M, N] = [matrix.length, matrix[0].length]
  let [left, right] = [0, M * N - 1]
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    const val = matrix[Math.floor(mid / N)][mid % N]
    if (val < target) {
      left = mid + 1
    } else if (val > target) {
      right = mid - 1
    } else {
      return true
    }
  }
  return false
}