class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (!m)
        {
            return false;
        }
        int n = matrix.at(0).size();
        if (!n)
        {
            return false;
        }
        int row = -1;
        for (int i = 0; i < m; i++)
        {
            if (matrix[i][0] <= target && matrix[i][n - 1] >= target) {
                row = i;
                break;
            }
        }

        if (row < 0)
        {
            return false;
        }

        //二分查找
        int low = 0, high = n - 1;
        vector<int> tVec = matrix.at(row);
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (tVec.at(mid) > target)
            {
                high = mid - 1;
            }
            else if (tVec.at(mid) < target){
                low = mid + 1;
            }
            else {
                return true;
            }
        }

        return false;
    }
};