y, it cannot be in A (all values there are less than y), so we search B, C, and D.

Approach

Base Case:
- If the submatrix is empty, return false.
Find Center:
- Compute the middle row and column.
- Compare the center value to the target.
Recursive Search:
- If equal, return true.
- If target < center, search top-left, top-right, and bottom-left quadrants.
- If target > center, search top-right, bottom-left, and bottom-right quadrants.

Pseudocode

def search(matrix, row_lo, row_hi, col_lo, col_hi, target):
    if row_lo > row_hi or col_lo > col_hi:
        return False
    row_mid = (row_lo + row_hi) // 2
    col_mid = (col_lo + col_hi) // 2
    mid = matrix[row_mid][col_mid]
    if mid == target:
        return True
    elif target < mid:
        return (
            search(matrix, row_lo, row_mid - 1, col_lo, col_mid - 1, target) or
            search(matrix, row_lo, row_mid - 1, col_mid, col_hi, target) or
            search(matrix, row_mid, row_hi, col_lo, col_mid - 1, target)
        )
    else:
        return (
            search(matrix, row_lo, row_mid - 1, col_mid + 1, col_hi, target) or
            search(matrix, row_mid + 1, row_hi, col_lo, col_mid, target) or
            search(matrix, row_mid, row_hi, col_mid + 1, col_hi, target)
        )

Code

[{"language":"C++","code":"class Solution {\n    bool search(const vector<vector<int>>& mat, int r1, int r2, int c1, int c2, int target) {\n        if (r1 > r2 || c1 > c2) return false;\n        int rm = (r1 + r2) / 2, cm = (c1 + c2) / 2;\n        int mid = mat[rm][cm];\n        if (mid == target) return true;\n        if (target < mid)\n            return search(mat, r1, rm - 1, c1, cm - 1, target) ||\n                   search(mat, r1, rm - 1, cm, c2, target) ||\n                   search(mat, rm, r2, c1, cm - 1, target);\n        else\n            return search(mat, r1, rm - 1, cm + 1, c2, target) ||\n                   search(mat, rm + 1, r2, c1, cm, target) ||\n                   search(mat, rm, r2, cm + 1, c2, target);\n    }\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int m = matrix.size(), n = matrix[0].size();\n        return search(matrix, 0, m - 1, 0, n - 1, target);\n    }\n};","lang":"cpp"},{"language":"Go","code":"func searchMatrix(matrix [][]int, target int) bool {\n    var search func(r1, r2, c1, c2 int) bool\n    search = func(r1, r2, c1, c2 int) bool {\n        if r1 > r2 || c1 > c2 { return false }\n        rm, cm := (r1+r2)/2, (c1+c2)/2\n        mid := matrix[rm][cm]\n        if mid == target { return true }\n        if target < mid {\n            return search(r1, rm-1, c1, cm-1) ||\n                   search(r1, rm-1, cm, c2) ||\n                   search(rm, r2, c1, cm-1)\n        }\n        return search(r1, rm-1, cm+1, c2) ||\n               search(rm+1, r2, c1, cm) ||\n               search(rm, r2, cm+1, c2)\n    }\n    m, n := len(matrix), len(matrix[0])\n    return search(0, m-1, 0, n-1)\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        return search(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);\n    }\n    private boolean search(int[][] mat, int r1, int r2, int c1, int c2, int target) {\n        if (r1 > r2 || c1 > c2) return false;\n        int rm = (r1 + r2) / 2, cm = (c1 + c2) / 2;\n        int mid = mat[rm][cm];\n        if (mid == target) return true;\n        if (target < mid)\n            return search(mat, r1, rm - 1, c1, cm - 1, target) ||\n                   search(mat, r1, rm - 1, cm, c2, target) ||\n                   search(mat, rm, r2, c1, cm - 1, target);\n        else\n

Related Tags