Search a 2D Matrix - Python Solution

1. Introduction

The "Search a 2D Matrix" problem is a classic example of applying binary search in a two-dimensional context. The challenge is to efficiently search for a target value in a matrix that has sorted rows and where each row starts with a number greater than the last number of the previous row. The goal is to implement a solution with a time complexity of O(log(m * n)), where m and n are the dimensions of the matrix.

Problem

Given an m x n integer matrix where each row is sorted in non-decreasing order and the first integer of each row is greater than the last integer of the previous row, determine if a given target integer is present in the matrix. The solution should have a time complexity of O(log(m * n)).

2. Solution Steps

1. Flatten the 2D matrix search space into a virtual 1D array.

2. Apply binary search on this virtual array.

3. Map the mid-point of the binary search to its corresponding row and column in the 2D matrix.

4. Compare the target with the element at the calculated row and column.

5. Adjust the search range based on the comparison.

3. Code Program

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

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = matrix[mid // cols][mid % cols]  # Convert 1D index to 2D coordinates

        # Compare mid_value with the target
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

# Testing the function with an example
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3))
print(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13))

Output:

True
False

Explanation:

1. Virtual 1D Array: The matrix is treated as a virtual 1D array for binary search purposes.

2. Binary Search: Standard binary search is applied, but with indices mapped to 2D matrix coordinates.

3. Mid-Value Calculation: The midpoint index in the virtual 1D array is mapped to its corresponding row and column in the 2D matrix.

4. Target Comparison: The target is compared with the value at the calculated mid-point.

5. Search Range Adjustment: Depending on whether the target is greater or less than the mid-value, the search range is adjusted accordingly.

6. Result: The function returns True if the target is found, otherwise False.