Search a 2D Matrix
Write an efficient algorithm that searches for a value in a 2D matrix. The matrix has the following properties: - Integers in each row are sorted from left to right. - The first integer of each row is greater than the last integer of the previous row. Given a target integer, return true if it exists in the matrix, otherwise return false.
Constraints:
- You must use an efficient algorithm with a time complexity better than O(n*m), where n is the number of rows and m is the number of columns.
- You can assume the input matrix is not empty and does not contain empty rows.
Examples:
Input: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Target: 3
Output: true
Explanation: The target value 3 exists in the matrix at position (0,1).
Solutions
Binary Search
Time: O(log(n*m))Space: O(1)
We treat the 2D matrix as a 1D sorted array and apply binary search. The key is to map the 1D index to the 2D matrix coordinates using the formula matrix[mid / cols][mid % cols].
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1
while low <= high:
mid = (low + high) // 2
mid_val = matrix[mid // cols][mid % cols]
if mid_val == target:
return True
if mid_val < target:
low = mid + 1
else:
high = mid - 1
return FalseFollow-up:
How would you modify the algorithm if the matrix is not sorted?
