题目

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

来源：力扣热题100 74. 搜索二维矩阵

---

思路（注意事项）

---

纯代码

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();for (int i = 0; i < m; i ++)if (target <= matrix[i][n - 1] && target >= matrix[i][0])for (int j = 0; j < n; j ++){int nl = 0, nr = n - 1;while (nl < nr){int mid = (nl + nr) / 2;if (matrix[i][mid] >= target) nr = mid;else nl = mid + 1;}if (matrix[i][nr] == target) return true;}return false;}
};

题解（加注释）

#include <vector>class Solution {
public:// 该函数用于在一个二维矩阵中查找目标值 target// 矩阵的每一行元素从左到右按升序排列，每行的第一个元素大于前一行的最后一个元素bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {// 获取矩阵的行数int m = matrix.size();// 获取矩阵的列数，假设矩阵至少有一行int n = matrix[0].size();// 遍历矩阵的每一行for (int i = 0; i < m; i++) {// 检查目标值是否可能在当前行中// 如果目标值小于等于当前行的最后一个元素且大于等于当前行的第一个元素if (target <= matrix[i][n - 1] && target >= matrix[i][0]) {// 在当前行中使用二分查找目标值// 初始化二分查找的左边界为 0int nl = 0;// 初始化二分查找的右边界为当前行的最后一个元素的索引int nr = n - 1;// 开始二分查找过程，只要左边界小于右边界，就继续循环while (nl < nr) {// 计算中间位置的索引int mid = (nl + nr) / 2;// 如果中间位置的元素大于或等于目标值// 说明目标值可能在左半部分或者就是中间位置，更新右边界为 midif (matrix[i][mid] >= target) {nr = mid;} // 否则，即中间位置的元素小于目标值// 说明目标值在右半部分，更新左边界为 mid + 1else {nl = mid + 1;}}// 当二分查找结束时，nl 和 nr 相等// 检查该位置的元素是否等于目标值if (matrix[i][nr] == target) {// 如果相等，说明找到了目标值，返回 truereturn true;} }}// 如果遍历完所有行都没有找到目标值，返回 falsereturn false;}
};