LeetCode热题100 搜索二维矩阵

题目描述给你一个满足下述两条属性的 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提示m matrix.lengthn matrix[i].length1 m, n 100−104matrix[i][j],target104-10^4 matrix[i][j], target 10^4−104matrix[i][j],target104思路进行两次二分查找模板第一次二分查找获取所在行第二次二分查找获取所在列。代码classSolution{public:boolsearchMatrix(vectorvectorintmatrix,inttarget){// 找到所在行的下一行vectorvectorint::iterator rowupper_bound(matrix.begin(),matrix.end(),target,[](constinta,constvectorintb){returnab[0];});// 所在行的下一行是第0行, 说明元素不存在if(rowmatrix.begin()){returnfalse;}// 找到所在行--row;// 对所在行进行二分查找returnbinary_search(row-begin(),row-end(),target);}};