# 240 - Search a 2D Matrix II

解法一 - 從左下往右上走

以上圖的例子來說，假設 target == 136 ，我們可以先從最左下角開始走，依序是

1. 因為 136>118，所以 118 那一行都肯定比 136 小，可以不用再考慮，所以往右移

2. 因為 136>126，所以往右移

3. 因為 136>131，所以往右移

4. 因為 136<138，所以 136 有可能在這一行，往上移動來尋找

   ...

依此類推直到找到為止。

那因為這個方法是在對角線上走，所以對一個 $m \times n$ 的矩陣來說，時間複雜度就是 O(m+n)。

實作起來也滿簡單的：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        else if(matrix[0].empty()) return false;

        int m = matrix.size(), n = matrix[0].size();

        int row = m-1, col = 0;
        while(row >= 0 && col < n) {
            if(matrix[row][col] == target) return true;
            else if(matrix[row][col] > target) row--;
            else if(matrix[row][col] < target) col++;
        }

        return false;
    }
};