题目描述
给你一个满足下述两条属性的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-104 <= matrix[i][j], target <= 104
解决方案：
核心逻辑
代码利用矩阵 “每行升序、行尾元素递增” 的特性，分两步完成查找：
- 定位目标行：遍历矩阵的每一行，通过比较
target与当前行的最后一个元素，找到第一个行尾元素 ≥target的行（目标值若存在，必在这一行）； - 单行二分查找：调用
lower_bound函数，在定位到的行中使用开区间二分法（left=-1、right=列数，循环条件left+1<right）查找target，找到则返回true，否则返回false； - 若遍历完所有行都未找到符合条件的行，直接返回
false。
总结
- 核心思路：先通过行尾元素快速缩小目标范围到某一行，再在该行内用二分查找精准定位，兼顾简洁性和效率；
- 关键设计：
lower_bound函数采用开区间二分法，简化了单行查找的边界处理； - 适用场景：仅适用于 “每行升序、行尾元素递增” 的二维矩阵，是该类矩阵查找的经典解法。
函数源码：
class Solution { public: bool lower_bound(vector<int>& nums,int left,int right, int x){ int len=nums.size(); int mid=0; while(left+1<right){ mid=(left+right)/2; if(nums[mid]<x) left=mid; else right=mid; } return nums[right]==x? true:false; } bool searchMatrix(vector<vector<int>>& matrix, int target) { int len=matrix.size(); int row_len=matrix[0].size(); for(int i=0;i<len;i++){ if(target<=matrix[i][row_len-1]){ return lower_bound(matrix[i],-1,matrix[i].size(),target); } } return false; } };
