Solution

• 二分查找每一行

class Solution {
public:
    // 把每一行看成有序递增的数组，利用二分查找
    bool Find(int target, vector<vector<int> > array) {
        int n = array.size();
        if (n == 0) return false;
        int m = array[0].size();
        for (int i = 0; i < n; ++i) {
            int l = 0, r = m;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (target > array[i][mid]) l = mid + 1;
                else if (target < array[i][mid]) r = mid;
                else return true;
            }
        }
        return false;
    }
};

• 反对角线查找

class Solution {
public:
    // 反对角线逼近（左下角 --> 右上角）
    bool Find(int target, vector<vector<int> > array) {
        int n = array.size();
        if (n == 0) return false;
        int m = array[0].size();
        
        int i = n - 1, j = 0; // 初始化，目的：为了两个方向上有不同的比较
        while (i >= 0 && j < m) {
            if (array[i][j] > target) --i;
            else if (array[i][j] < target) ++j;
            else return true;
        }
        return false;
    }
};