Search a Sorted 2D Matrix

Given a 2D matrix where each row is sorted in ascending order, and the first integer of each row is greater than the last integer of the previous row, you need to efficiently determine if a given target value exists within the matrix. This is a common problem in data processing and algorithm design, as it tests your ability to leverage sorted data for optimized searching.

Problem Description

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

1. Rows are sorted: Each row is sorted in ascending order from left to right.
2. Row dependency: The first integer of each row is greater than the last integer of the previous row.

Your task is to implement a function that takes this matrix and an integer target as input and returns TRUE if the target exists in the matrix, and FALSE otherwise.

Key Requirements:

• The search algorithm should be efficient, taking advantage of the sorted nature of the matrix.
• The function should handle all possible valid inputs according to the constraints.

Expected Behavior:

• If the target is found anywhere in the matrix, return TRUE.
• If the target is not found in the matrix, return FALSE.

Edge Cases to Consider:

• An empty matrix.
• A matrix with only one row or one column.
• The target being the smallest or largest element in the matrix.
• The target being outside the range of values in the matrix.

Examples

Example 1:

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

Output: TRUE

Explanation: The target value 3 is present in the first row of the matrix.

Example 2:

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

Output: FALSE

Explanation: The target value 13 is not present in the matrix.

Example 3:

Input:
matrix =
[
  [1]
]
target = 1

Output: TRUE

Explanation: The matrix contains only one element, which matches the target.

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^9 <= matrix[i][j], target <= 10^9
• The matrix is guaranteed to satisfy the sorting properties described in the problem description.

Notes

The properties of the matrix (sorted rows and row dependency) strongly suggest that a binary search approach can be adapted for this problem. Consider how you might flatten the 2D matrix into a 1D sorted array conceptually, and then apply binary search. This would allow for a time complexity better than a simple linear scan of all elements.