# 1. Introduction

"Search a 2D Matrix II" is a problem that combines matrix traversal with binary search principles. The challenge lies in efficiently searching for a target value in a 2D matrix where each row and each column is sorted in ascending order. This problem tests the ability to apply search algorithms in a two-dimensional space with sorted data.

## Problem

Given an m x n integer matrix where each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom, write an efficient algorithm to search for a target value in the matrix. The algorithm should return true if the target is found and false otherwise.

# 2. Solution Steps

2. If the target is greater than the current element, move down a row.

3. If the target is less than the current element, move left a column.

4. Repeat steps 2 and 3 until the target is found or the bounds of the matrix are exceeded.

5. Return true if the target is found, otherwise false.

# 3. Code Program

``````def searchMatrix(matrix, target):
if not matrix:
return False

rows, cols = len(matrix), len(matrix[0])
row, col = 0, cols - 1

while row < rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
row += 1
else:
col -= 1

return False

# Example Usage
matrix = [
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(searchMatrix(matrix, 5))  # Output: True
print(searchMatrix(matrix, 20)) # Output: False

``````

```True
False
```

### Explanation:

1. Matrix Properties: Utilizes the properties of the matrix having sorted rows and columns.

2. Efficient Search: Begins the search from the top right corner, allowing elimination of either a row or a column in each step.

3. Directional Movement: Moves either down (if the target is larger) or left (if the target is smaller).

4. Termination: The search terminates when the target is found or when the search space is exhausted.

5. Optimized Algorithm: Provides an O(m + n) time complexity solution, more efficient than a brute force approach.

6. Result: Returns true if the target is found in the matrix, otherwise false.