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

知识点

二分

思路

观察到题意所示的矩阵，左上的点一定比右下的点大，展开来看也是二分的，所以可以使用二分的做法，初始化i为0，j为n-1，代表第一行最后一列的点。用i，j来维护数组中当前检索到的点matri[i][j]，若大了，则j--，否则i++，这样子就可以维护到一个“中间”的点，值为target

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @param target int整型 
     * @return bool布尔型
     */
    bool searchMatrix(vector<vector<int> >& matrix, int target) {
        // write code here
        int n=matrix[0].size();//初始化
        int i=0,j=n-1;//i为0，j为n-1，即从右上开始往左下走。换方向同理
        while(matrix[i][j]!=target)
        {
            if(matrix[i][j]>target)i++;
            else j--;
            if(i==n||j==-1)return false;//到达边界还没找到那就是没有这个数
        }
        return true;

    }
};