Coding - Search a 2D Matrix

Problem Statement: Search a 2D Matrix

Description

You are given an m x n integer matrix matrix with the following two 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; otherwise, return false.

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

Constraints

• m == matrix.length
• n == matrix[i].length
• 0 <= m, n <= 200
• -200 <= target < 200

Examples

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

Hints

1. The matrix is sorted in a special way. Can you take advantage of this?
2. You can solve this problem in O(log(m * n)) time complexity. How?