104. Search a 2D Matrix

Medium · Array

You are given an m × n integer matrix where each row is sorted in ascending order from left to right, and the first element of each row is greater than the last element of the previous row. In other words, the entire matrix is sorted as if it were a single flattened array.

Given a target value, determine whether the target exists in the matrix. Return true if found, false otherwise.

You must write a solution with O(log(m × n)) time complexity.

Examples

Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: The target 3 is found at position [0][1] in the matrix.
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: The target 13 does not exist in the matrix.

Constraints