74.搜索二维矩阵

题目

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

解法

class Solution {
public:
    bool searchMatrix(vector<vector<int>> matrix, int target) {
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
            return b < a[0];
        });
        if (row == matrix.begin()) {
            return false;
        }
        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};

演示upper_bound比较的过程

好的，让我们通过一个具体的例子来演示 upper_bound 的比较过程。

示例矩阵

假设我们有以下的二维矩阵 matrix 和目标值 target：

vector<vector<int>> matrix = {
    {1, 3, 5},
    {7, 10, 11},
    {12, 14, 16},
    {20, 22, 24}
};
int target = 9;

upper_bound 的使用

在这个例子中，我们要找到 target（9）在 matrix 中的可能位置。我们使用 upper_bound：

auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
    return b < a[0];
});

比较过程

• matrix.begin() 指向第一行 {1, 3, 5}，第一个元素是 1。
• matrix.end() 指向超出最后一行的迭代器，表示没有更多行。

比较步骤

1. 第一轮比较：

   • b = 9，a = {1, 3, 5}。
   • 判断 9 < 1，结果为 false。
   • 因为 false，upper_bound 继续检查下一行。

2. 第二轮比较：

   • b = 9，a = {7, 10, 11}。
   • 判断 9 < 7，结果为 false。
   • 继续检查下一行。

3. 第三轮比较：

   • b = 9，a = {12, 14, 16}。
   • 判断 9 < 12，结果为 true。
   • 此时，upper_bound 找到了第一个大于 9 的行，因此返回该行的迭代器。

结果

• row 现在指向 {12, 14, 16} 这一行的开始位置。
• 然后我们执行 --row，将其移动到 {7, 10, 11} 这一行。
• 最后在 {7, 10, 11} 这一行使用 binary_search 查找 target（9）。

总结

在这个例子中，upper_bound 找到的是第一个大于 9 的行（{12, 14, 16}），而在实际查找中，我们确定 9 可能在 {7, 10, 11} 这一行中。通过这种方式，upper_bound 允许我们快速定位目标值可能出现的行。希望这个例子能帮助你理解 upper_bound 的比较过程！