74. 搜索二维矩阵

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

每行中的整数从左到右按非递减顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

> 代码

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

        return matrix[t][r] == target ? 1:0;
    }
};