Search in a Row-and-Column Sorted 2D Matrix

You are given an m x n matrix in which each row is sorted in strictly increasing order from left to right, and the first element of every row is strictly greater than the last element of the previous row - so the matrix reads as one long sorted sequence when scanned row by row. Given an integer target, determine whether it exists anywhere in the matrix. Your algorithm must run in O(log(m*n)) time.

Input: The first line contains two integers m and n. Each of the next m lines contains n space-separated integers, one row of the matrix. The last line contains the integer target. Output: Print YES if target exists anywhere in the matrix, otherwise print NO.

1 <= m, n <= 1000 1 <= m*n <= 10^6 -10^9 <= matrix[i][j], target <= 10^9

The specific guarantee here (each row's first element exceeds the previous row's last element) is exactly what makes the 'treat it as one flat sorted array' reduction valid - a matrix merely sorted independently by row AND by column, without this guarantee, would need a fundamentally different technique.

Search for a target in a matrix where each row is sorted, and every row continues seamlessly from where the previous row left off. Brute force: Search each row individually with its own binary search, or scan the whole matrix linearly - both work, but ignore the special guarantee that the WHOLE matrix, read row by row, forms one continuous sorted sequence, which allows a single unified binary search instead of m separate ones. Optimised: Since the matrix, read in row-major order, is EXACTLY equivalent to one long sorted array, a single binary search over 'flat' indices (using simple division/modulo to map back to row/column) finds the target in O(log(m*n)) - much better than any row-by-row search strategy.

1. Treat the matrix as ONE single flat sorted array of length m*n conceptually, without physically flattening it. 2. Map a flat index k to its actual matrix position: row = k / n, column = k % n. 3. Run a standard binary search over flat indices 0 to m*n-1, using this mapping to fetch each candidate's actual value for comparison.

Time: O(log(m*n)) - a single binary search over the conceptual flat array. Space: O(1) - no extra data structure, just the index-mapping arithmetic.

m = 1 or n = 1 (a single row or single column); target smaller than matrix[0][0] or larger than matrix[m-1][n-1].

Be ready to contrast this with the DIFFERENT (and more general) 'search in a matrix where rows AND columns are each sorted independently, but rows don't continue from each other' problem - that harder variant needs a staircase-walk technique instead, since the flat-array trick doesn't apply there.