Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-109 <= target <= 109

我的答案：
一下子就想到binary search，好久不写也觉得有点陌生了

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_end = matrix.size();
        int col_end = matrix[0].size();
        
        for (int r=0; r<row_end; ++r) {
            int c = BinarySearch(matrix[r], col_end, target);
            if (matrix[r][c] == target)
                return true;
            col_end = c+1;
        }
        
        return false;
    }
    int BinarySearch(const vector<int>& matrix_row, const int& col_end, const int& target) {
        if (target > matrix_row[col_end-1])
            return col_end-1;
        int c_left = 0;
        int c_right = col_end;
        int c_mid = (c_left+c_right)/2;
        while (c_left < c_right) {
            if (matrix_row[c_mid] == target)
                return c_mid;
            else if (matrix_row[c_mid] > target) {
                c_right = c_mid;
            }
            else {
                c_left = c_mid+1;
            }
            c_mid = (c_left+c_right)/2;
        }
        return c_left;
    }
};

Runtime: 264 ms, faster than 19.54% of C++ online submissions for Search a 2D Matrix II.
Memory Usage: 11.1 MB, less than 17.69% of C++ online submissions for Search a 2D Matrix II.

性能一般，应该是O(nlogn)

看答案：
https://zxi.mytechroad.com/blog/two-pointers/leetcode-240-search-a-2d-matrix-ii/
只需要从右上角开始往left或者bottom搜索就可以了，不用binary search。O(n)

我的默写：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_end = matrix.size();
        int col_end = matrix[0].size();
        
        int r = 0, c = col_end-1;
        while (r<row_end and c>=0) {
            if (matrix[r][c] == target) 
                return true;
            else if (matrix[r][c] > target)
                --c;
            else
                ++r;
        }
        return false;
    }
};

Runtime: 104 ms, faster than 75.42% of C++ online submissions for Search a 2D Matrix II.
Memory Usage: 10.9 MB, less than 55.95% of C++ online submissions for Search a 2D Matrix II.

想了想为什么比binary search快，binary search快在没有每一层联系的时候