三门峡市网站建设_网站建设公司_ASP.NET_seo优化

题目描述

给你一个满足下述两条属性的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

解决方案：

核心逻辑

代码利用矩阵 “每行升序、行尾元素递增” 的特性，分两步完成查找：

1. 定位目标行：遍历矩阵的每一行，通过比较target与当前行的最后一个元素，找到第一个行尾元素 ≥target的行（目标值若存在，必在这一行）；
2. 单行二分查找：调用lower_bound函数，在定位到的行中使用开区间二分法（left=-1、right=列数，循环条件left+1<right）查找target，找到则返回true，否则返回false；
3. 若遍历完所有行都未找到符合条件的行，直接返回false。

总结

1. 核心思路：先通过行尾元素快速缩小目标范围到某一行，再在该行内用二分查找精准定位，兼顾简洁性和效率；
2. 关键设计：lower_bound函数采用开区间二分法，简化了单行查找的边界处理；
3. 适用场景：仅适用于 “每行升序、行尾元素递增” 的二维矩阵，是该类矩阵查找的经典解法。

函数源码：

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; } };