Search a 2D Matrix

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

• Each row is sorted in non-decreasing order from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return True if target is in matrix, or False otherwise.

You must write a solution in O(log(m * n)) time.

---

Example 1

 1   3   5   7
10  11  16  20
23  30  34  60

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: True
Explanation: 3 is in the first row at index 1.

Example 2

 1   3   5   7
10  11  16  20
23  30  34  60

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: False
Explanation: 13 does not appear in the matrix.

---

Constraints

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