74. 搜索二维矩阵
编写一个高效的算法来判断m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
题解
第一次二分查找第一列的数据，确定列，找到最后一个满足val<=target的数据。然后对此列做二分查找，寻找是否存在target值。
查看代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int l=0,r=matrix.size()-1;//第一次二分
while(l<r){
int mid=(l+r+1)/2;
if(matrix[mid][0]<=target){//寻找最后一个满足<=target的值
l=mid;
}
else
r=mid-1;
}
if(l<r)
return false;
int l2=0;//第二次二分
r=matrix[l].size()-1;
while(l2<=r){
int mid=(l2+r)/2;
if(matrix[l][mid]==target)
return true;
if(matrix[l][l2]<=target&&matrix[l][mid]>=target){
r=mid-1;
}
else
l2=mid+1;
}
return false;
}
};