Poison

240. Search a 2D Matrix II

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (findTarget(row, target)) {
                return true;
            }
        }

        return false;
    }

    private boolean findTarget(int[] row, int target) {
        int left = 0, right = row.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (row[mid] < target) {
                left = mid + 1;
            } else if (row[mid] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }

        return false;
    }
}
Matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            int cell = matrix[i][j];
            if (cell < target) {
                j++;
            } else if (cell > target) {
                i--;
            } else {
                return true;
            }
        }

        return false;
    }
}
在行列上进行二分搜索失败的原因

注意题目只说了每一行从左到右升序，每一列从上到下升序，并没有说第二行所有元素一定大于第一行所有元素，比如以下数组：

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

当搜索 5 时，我们不能采取先定位至第 3 行 [3, 6, 9, 16, 22] 再搜索 5 的方式，因为这样会错过目标值。5 大于第 3 行的首个元素，此时可能位于前三行而不是一定位于第三行，所以我们不能排除第一行与第二行。

类似地：

1
2
3
4
5
6
7
[
    [1,  2,   3,  4,  5],
    [6,  7,   8,  9, 10],
    [11, 12, 13, 14, 15],
    [16, 17, 18, 19, 20],
    [21, 22, 23, 24, 25]
]

当搜索 19 时，我们不能采取先定位至第 5 列 [5, 10, 15, 20, 25] 再搜索 19 的方式，因为这样会错过目标值。19 大于第 5 列的首个元素，不代表 19 一定存在于第 5 列。

Binary Search + Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        return searchMatrix(matrix, 0, m - 1, 0, n - 1, m, n, target);
    }

    private boolean searchMatrix(int[][] matrix, int startRowIndex, int endRowIndex, int startColIndex, int endColIndex, int rows, int cols, int target) {
        // 注意此处的判断条件，除了必须在矩阵内部搜索，还需要起始索引小于等于终止索引，否则递归无法终止
        if (startRowIndex < 0 || startRowIndex == rows || startColIndex < 0 || startColIndex == cols ||
                endRowIndex < 0 || endRowIndex == rows || endColIndex < 0 || endColIndex == cols ||
                startRowIndex > endRowIndex || startColIndex > endColIndex) {
            return false;
        }

        // only one element
        if (startRowIndex == endRowIndex && startColIndex == endColIndex) {
            return matrix[startRowIndex][startColIndex] == target;
        }

        int midRowIndex = (startRowIndex + endRowIndex) >>> 1;
        int midColIndex = (startColIndex + endColIndex) >>> 1;
        if (matrix[midRowIndex][midColIndex] < target) {
            return searchMatrix(matrix, midRowIndex + 1, endRowIndex, startColIndex, midColIndex, rows, cols, target) ||
                    searchMatrix(matrix, startRowIndex, midRowIndex, midColIndex + 1, endColIndex, rows, cols, target) ||
                    searchMatrix(matrix, midRowIndex + 1, endRowIndex, midColIndex + 1, endColIndex, rows, cols, target);
        } else {
            return searchMatrix(matrix, midRowIndex + 1, endRowIndex, startColIndex, midColIndex - 1, rows, cols, target) ||
                    searchMatrix(matrix, startRowIndex, midRowIndex - 1, midColIndex + 1, endColIndex, rows, cols, target) ||
                    searchMatrix(matrix, startRowIndex, midRowIndex, startColIndex, midColIndex, rows, cols, target);
        }
    }
}
Reference

240. Search a 2D Matrix II
剑指 Offer 04. 二维数组中的查找
详细通俗的思路分析，多解法