Matrix Search

You are given an m x n integer matrix matrix with the following properties:

• Each row is sorted in ascending order.
• The first element of each row is strictly greater than the last element of the previous row.

Given an integer target, return true if target exists anywhere in matrix, or false otherwise, in O(log(m * n)) time.

Example 1

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

Example 2

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

Constraints

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