搜索二维矩阵

题目链接：搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

方法一：两次二分查找

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int u = -1,d = matrix.size();
        while (u + 1 < d) {
            int mid = (u+d)/2;
            if (matrix[mid][0] <= target) u = mid;
            else d = mid;
        }
        int l = -1,r = matrix[0].size();
        if (u == -1) u = 0;
        while (l+1 < r) {
            int mid = (l+r) / 2;
            if (matrix[u][mid] == target) return true;
            else if (matrix[u][mid] > target) r = mid;
            else l = mid;
        }
        return false;
    }
};

方法二：查找

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int x = matrix.size() - 1;
        int y = 0;
        while (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()) {
            if (matrix[x][y] == target) return true;
            if (matrix[x][y] > target) x--;
            else y++;
        }
        return false;
    }
};