434. Check if Target Exists in Sorted 2D Matrix

Given an m×n matrix where each row is sorted left-to-right and the first element of each row is greater than the last element of the previous row, determine if target exists in the matrix. Solve in O(log(m*n)).

Input: A 2D sorted integer matrix and integer target.

Output: true if target exists, false otherwise.

Examples

Input: [[1,3,5,7],[9,11,13,15],[17,19,21,23]], 13
Output: true
Explanation: Treat as flat sorted array. index 10 → row=10//4=2, col=10%4=2 → matrix[2][2]=21. Binary search finds 13 at index 6.

Input: [[1,3,5,7],[9,11,13,15],[17,19,21,23]], 14
Output: false
Explanation: 14 is not present; binary search returns false.

Input: [[1]], 1
Output: true
Explanation: Single element equals target.

Constraints

• m == matrix.length
• n == matrix[0].length
• 1 <= m,n <= 100
• -10^4 <= matrix[i][j],target <= 10^4

Asked by