Write an efficient algorithm to search for a target value in an m x n matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row.

Input: matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 → Output: trueInput: matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=13 → Output: false

Treat the matrix as a flat sorted array of m*n elements. Binary search using virtual index mid, and convert to row/col using row=mid/n, col=mid%n.

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int lo = 0, hi = m * n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int val = matrix[mid / n][mid % n]; if (val == target) return true; else if (val < target) lo = mid + 1; else hi = mid - 1; } return false; } }