Search a 2D Matrix

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

Each row is sorted in non-decreasing order.
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 that runs in O(log(m * n)) time.

Example 1

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

Inputmatrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Outputtrue

The value 3 appears in the first row of the matrix.

Example 2

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

Inputmatrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Outputfalse

The value 13 does not appear anywhere in the matrix.

Constraints