Search a Sorted Matrix

Each row of matrix is sorted in increasing order, and the first value of each row is bigger than the last value of the row above. So reading the rows one after another gives one sorted list. Return True if target is in the matrix.

Examples

Example 1

Input:

search_matrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3)

Output:

True

Example 2

Input:

search_matrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13)

Output:

False

Constraints

• 0 <= rows, cols, and rows * cols <= 2 * 10**5
• Rows are sorted and each row starts after the previous one ends.
• -10**9 <= matrix[i][j], target <= 10**9
• The big tests count how many cells you read.