74、搜索二维矩阵

题目：

解答：

两次二分查找即可。如果出现down=-1，说明matrix[0][0]<target 那么所有数都小于target，return false即可。

第一次闭区间查找，最后upper=down+1,在down这一行查找即可。

如果出现upper越界，也就是down指向最后一行，只能说明matrix[m][0]>target,并不能说明最后一行所有数都大于target

第二次二分查找，如果没找到，循环结束后return false，否则找到时return true。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();int upper = 0,down = m-1,left=0,right=n-1;while(upper<=down){int mid = upper+(down-upper)/2;if(matrix[mid][0]==target)return true;else if(matrix[mid][0]<target)upper = mid + 1;elsedown = mid - 1;}if(down == -1) return false;while(left<=right){int mid = left+(right-left)/2;if(matrix[down][mid]==target)return true;else if(matrix[down][mid]<target)left=mid+1;else right=mid-1;}return false;}
};

时间复杂度O(log(mn))

空间复杂度O(1)