搜索二维矩阵

题目

编写一个高效的算法来判断 matrix 矩阵中, 判断是否存在一个目标值 target. 该矩阵具有如下特性:

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

提示:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10⁴ <= matrix[i][j], target <= 10⁴

示例

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

输出: true

题解

看到已排序的数组找某个值, 就先想到二分查找. 虽然这是个二维数组, 但你仍然可以看成一个一维数组.

1. 先算出二维数组的总长度 m * n, 那么 right 就是 m * n - 1
2. 下面是常规的二分查找套路, 只不过找到 mid 对应的元素稍微费事些: matrix[(mid / n) | 0][mid % n]

JavaScript

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  const m = matrix.length
  const n = matrix[0].length

  let left = 0
  let right = m * n - 1

  while (left <= right) {
    const mid = ((left + right) / 2) | 0
    const midNum = matrix[(mid / n) | 0][mid % n]

    if (midNum < target) {
      left = mid + 1
    } else if (midNum > target) {
      right = mid - 1
    } else {
      return true
    }
  }

  return false
}

Rust

pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let (m, n) = (matrix.len(), matrix[0].len());
    let (mut left, mut right) = (0, m * n - 1);

    while left <= right {
        let mid = (left + right) / 2;
        let mid_num = matrix[mid / n][mid % n];

        if (mid_num < target) {
            left = mid + 1;
        } else if mid_num > target {
            if (mid == 0) {
                break;
            }

            right = mid - 1;
        } else {
            return true;
        }
    }

    return false;
}

复杂度分析

时间复杂度: O(log(m * n)) 空间复杂度: O(1)