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].
function searchMatrix(matrix, target) {
const rows = matrix.length;
const cols = matrix[0].length;
let low = 0;
let high = rows * cols - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const midVal = matrix[Math.floor(mid / cols)][mid % cols];
if (midVal === target) return true;
if (midVal < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
Follow-up:
How would you modify the algorithm if the matrix is not sorted?
