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].
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = matrix.size();
int cols = matrix[0].size();
int low = 0;
int high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = matrix[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?
