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.length
n == matrix[i].length
1 <= m, n <= 100
−104<=matrix[i][j],target<=104-10^4 <= matrix[i][j], target <= 10^4−104<=matrix[i][j],target<=104

思路

进行两次二分查找模板，第一次二分查找获取所在行，第二次二分查找获取所在列。

代码

classSolution{public:boolsearchMatrix(vector<vector<int>>&matrix,inttarget){// 找到所在行的下一行vector<vector<int>>::iterator row=upper_bound(matrix.begin(),matrix.end(),target,[](constinta,constvector<int>&b){returna<b[0];});// 所在行的下一行是第0行, 说明元素不存在if(row==matrix.begin()){returnfalse;}// 找到所在行--row;// 对所在行进行二分查找returnbinary_search(row->begin(),row->end(),target);}};