If you were to imagine the 2D Matrix as a 1D array instead, clearly it would be sorted in the ascending order as per the conditions. This is because each row is sorted in ascending order and the first element of a row is larger than the last element of the previous row. See below:
[1, 3, 5, 7]
[10, 11, 16, 20] ---> [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 50]
[23, 30, 34, 50]
We know that we can apply binary search in a 1D array and it takes up O(lg n) time. All we have to do here is to somehow map the indices of the 2D array into the index of a 1D array.
- n * m matrix convert to an array => matrix[x][y] => a[x * m + y]
- an array convert to n * m matrix => a[x] => matrix[x / m][x % m];
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)
return false;
int rows = matrix.size(), cols = matrix[0].size();
int l = 0, r = rows*cols-1;
while (l<=r) {
int mid = l + (r-l)/2;
int x = mid/cols, y = mid%cols;
if (matrix[x][y] == target)
return true;
if (matrix[x][y] > target)
r = mid-1;
else
l = mid+1;
}
return false;
}
};
Time complexity: O(lg(n*m)) where n is the number of rows and m is the number of columns
Space complexity: O(1)