题解 | #二维数组中的查找#

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        // length and width of the board
        int l = array.size();
        int w = array[0].size();
        if (l==0 || w==0) return false;
        // indices of row and column
        int r = 0;
        int c = w-1;
        while (target!=array[r][c]){
            if (target<array[r][c]) c-=1;
            else r+=1;
            if (r<0 || r>l-1 || c<0 || c>w-1) break;
        }
        if (r<0 || r>l-1 || c<0 || c>w-1) return false;
        else return true;
    }
};

从右上角开始查询，因为这样在每一个位置 [i][j] 都有两个选项，

1. 如果目标数比当前数小，往左走 j-=1，并且因为数字从上到下从小到大排序，可以同时排除所有 j 列该数下方的数字；
2. 如果目标数比当前数大，往下走 i+=1，并且因为数字从左往右从小到大排序，可以同时排除所有 i 行该数左边的数字；