74. Search a 2D Matrix

题目链接

https://leetcode.com/problems/search-a-2d-matrix/

解题思路

二分查找

代码

class Solution {
public:
    bool dfs(vector<vector<int>> &matrix, int &target, int up, int down, int left, int right) {
        if (down < up || right < left)  {
            return false;
        }

        int i = (up + down) / 2, j = (left + right) / 2;
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] < target) {
            return dfs(matrix, target, i + 1, down, left, j) || dfs(matrix, target, i, down, j + 1, right);
        } else {
            return dfs(matrix, target, up, i, left, j - 1) || dfs(matrix, target, up, i - 1, j, right);
        }
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int up = 0, down = matrix.size() - 1;
        if (down < up) {
            return false;
        }
        int left = 0, right = matrix[0].size() - 1;
        return dfs(matrix, target, up, down, left, right);
    }
};