搜索二维矩阵(回溯)

给你一个满足下述两条属性的 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：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n =matrix[0].size();
        //针对每行进行二分搜索
        for(int i=0;i<m;i++){
            if(matrix[i][0]>target){//该行第一个元素就大于target,提前终止搜索
                return false;
            }
            int left = 0,right = n-1;
            while(left<=right){
                int mid = left+(right-left)/2;
                if(matrix[i][mid]==target){
                    return true;
                }else if(matrix[i][mid]>target){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
        }
        return false;
    }
};