C++ two solutions (O(m+n), O(mlogn))
O(m+n) solution\n\n        bool searchMatrix(vector>& matrix, int target) {\n        int i = 0;\n        int j = matrix[0].size() - 1;\n        \n        while(
1. O(m+n) solution\n\n        bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int i = 0;\n        int j = matrix[0].size() - 1;\n        \n        while(i < matrix.size() && j >= 0) {\n            if(matrix[i][j] == target)\n                return true;\n            \n            if(matrix[i][j] < target)\n                i++;\n            else\n                j--;\n        }\n        \n        return false;\n        }\n\n\n\n\n2. O(mlogn) solution\n\n        bool searchMatrix(vector<vector<int>>& matrix, int target) {\n\t\treturn searchMatrix(matrix, target, 0, matrix.size() - 1);\n\t    }\n\n\t    bool searchMatrix(vector<vector<int>>& matrix, int target, int top, int bottom) {\n\t\tif (top > bottom)\n\t\t\treturn false;\n\n\t\tint mid = top + (bottom - top) / 2;\n\t\tif (matrix[mid].front() <= target && target <= matrix[mid].back())\n\t\t\tif (searchVector(matrix[mid], target)) return true;\n\n\t\tif (searchMatrix(matrix, target, top, mid - 1)) return true;\n\t\tif (searchMatrix(matrix, target, mid + 1, bottom)) return true;\n\n\t\treturn false;\n\t    }\n\n\t    bool searchVector(vector<int>& v, int target) {\n\t\tint left = 0, right = v.size() - 1;\n\n\t\twhile (left <= right) {\n\t\t\tint mid = left + (right - left) / 2;\n\t\t\tif (v[mid] == target)\n\t\t\t\treturn true;\n\t\t\tif (v[mid] < target)\n\t\t\t\tleft = mid + 1;\n\t\t\telse\n\t\t\t\tright = mid - 1;\n\t\t}\n\n\t\treturn false;\n\t    }
[]