class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = m ? matrix[0].size() : 0, lo = 0, hi = m - 1;
        if (!m || !n)return false;
        //find column start with largest value lower than target
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            int curr = matrix[mid][0];
            if (curr < target)lo = mid + 1;
            else if (curr > target)hi = mid - 1;
            else return true;
        }
        if (hi < 0)return false;
        int i = hi;
        lo = 0, hi = n - 1;
        //find in row
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            int curr = matrix[i][mid];
            if (curr < target)lo = mid + 1;
            else if (curr > target)hi = mid - 1;
            else return true;
        }
        return false;
    }
};