剑指 Offer 04. 二维数组中的查找

题目链接

04. 二维数组中的查找

思路分析

利用右上角的数来判断减少判断行数，如果右上角的数大于target那么该列都大于，所以j–，如果小于target那么改行都小于，所以i++。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        std::ios::sync_with_stdio(false);
        if(matrix.empty()) return false;
        int i = 0, j = matrix[0].size() - 1, n = matrix.size();
        while(i < n && j >= 0){
            if(matrix[i][j] == target) return true;
            if(matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
};