74. Search a 2D Matrix

Leetcode Array Binary Search

Write an efficient algorithm that searches for a value in an $m \times n$ matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

分析

看到这道题目的时候，看到搜索，首先联想到是二分法。但是一般情况下，使用二分法的对象是一维数组，这里的二维数组怎么处理呢？一种直接的想法就是，首先找到目标所在的行，然后找到所在的列。时间复杂度是$O(\log(m) + \log(n))$。过程中需要特别注意出现空数组([[ ]], [ ])的情况。

public boolean searchMatrix(int[][] matrix, int target) {

    int m = matrix.length;
    if (m == 0) return false;
    int n = matrix[0].length;
    if (n == 0) return false;


    //find row
    int row;
    int lo = 0, hi = m - 1;
    while (lo <= hi) {
        int mid = (hi + lo) >>> 1;
        int cmp = matrix[mid][n - 1] - target;
        if (cmp > 0) hi = mid - 1;
        else if (cmp < 0) lo = mid + 1;
        else return true;
    }
    row = lo;

    // check row
    if (row > m - 1) return false;

    //find column
    int col;
    lo = 0; hi = n - 1;
    while (lo <= hi) {
        int mid = (hi + lo) >>> 1;
        int cmp = matrix[row][mid] - target;
        if (cmp > 0) hi = mid - 1;
        else if (cmp < 0) lo = mid + 1;
        else return true;
    }
    col = lo - 1;

    return false;
}

但是这种写法，真的有点复杂，而且非常容易出错，反正我写的过程中出现了不少小的错误。有没有更简单、更直接的方法呢？当然是有的！直接把二维数组看成是一维数组，唯一需要变动的是lo, hi和下标的处理:

int lo = 0;
int hi = m * n - 1;
int mid = (lo + hi) >>> 1;
// access
matrix[mid/n][mid%n]

完整的代码如下：

它的算法复杂度和第一种方案一样，也是$O(\log(mn))$.

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    if (m == 0) return false;
    int n = matrix[0].length;
    if (n == 0) return false;

    int lo = 0, hi = m*n - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        int cmp = matrix[mid/n][mid%n] - target;
        if (cmp > 0) hi = mid - 1;
        else if (cmp < 0) lo = mid + 1;
        else return true;
    }
    return false;
}