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

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

        int l = 0;
        int h = n-1;

        while(l <= h )
        {
            int mid = (l + (h-l)/2);

            if(target >= matrix[mid][0] && target <= matrix[mid][m-1])
                return binarysearch(matrix[mid], m, target);

            else if(target > matrix[mid][0]) l = mid+1;
            else h = mid-1;
        }


        return false;
    }

    bool binarysearch( vector<int>a, int m, int target )
    {
        int l = 0;
        int r = m-1;

        while( l <= r)
        {
            int mid = (l + r)/2;
            if( a[mid] > target )r = mid-1;
            if( a[mid] < target )l = mid+1;
           if(a[mid] == target) return true;
        }
        return false;
    }
};