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; } };