题解 | #寻找牛群中的特定编号牛#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是在二维有序数组中进行查找。

题目解答方法的文字分析

给定的二维数组满足以下条件：

1. 每一行的元素是降序排列的。
2. 下一行的第一个元素小于上一行的最后一个元素。

我们要在线性时间内完成查找编号为 target 的牛是否存在。为了实现这个目标，我们利用了二分法进行优化。

思路：由于每一行的元素是降序排列的，我们可以从二维数组的右上角开始，逐步缩小搜索范围。在每次迭代中，我们比较当前指向的元素和目标值 target 的大小：

• 如果当前元素等于 target，则找到目标牛，返回 true。
• 如果当前元素大于 target，则目标牛可能在当前元素的下方，因为每一行的元素是降序排列的，所以我们将指针 row 向下移动一位。
• 如果当前元素小于 target，则目标牛可能在当前元素的左侧，因为每一列的元素也是降序排列的，所以我们将指针 col 向左移动一位。

重复执行上述步骤，直到找到目标牛或者超出数组边界。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @param target int整型 
     * @return bool布尔型
     */
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 获取二维数组的行数和列数
        int m = matrix.size();
        int n = matrix[0].size();

        // 从右上角开始搜索
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                // 找到目标牛
                return true;
            } else if (matrix[row][col] > target) {
                // 当前元素大于目标值，目标牛可能在当前元素的下方
                row++;
            } else {
                // 当前元素小于目标值，目标牛可能在当前元素的左侧
                col--;
            }
        }

        // 在循环中未找到目标牛，返回 false
        return false;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！