74. Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in $O(log(m * n))$ time complexity.

一个漂亮思路

在力扣评论区看到一个非常漂亮的思路，虽然简单质朴，但是实在是太美丽了。

| 1 | 2 | 3 |

| 4 | 5 | 6 |

| 7 | 8 | 9 |

细心的你或许发现了，从右上角看这就是一个二叉搜索树！

解答如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rowLength = matrix[0].size();
        int colLength = matrix.size();
        int x {0};
        int y {rowLength - 1};
        while (x < colLength && y >= 0) {
            int value = matrix[x][y];
            if (value == target) {
                return true;
                break;
            } else if (target > value) {
                x++;
            } else {
                y--;
            }
        }
        return false;
    }
};

其实力扣还有个搜索二维矩阵II，用这个思路也可以做。

---

这个解法实在是太美丽了。水一篇