Write an efficient algorithm that searches for a value in an m x n matrix. This 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.
Brute Force
There are MN elements in the matrix, regardless the sorting properties, we can iterate the matrix to find the target in O(MN) complexity.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { for (const auto &n: matrix) { for (const auto &m: n) { if (m == target) { return true; } } } return false; } }; |
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (const auto &n: matrix) {
for (const auto &m: n) {
if (m == target) {
return true;
}
}
}
return false;
}
};The brute force is a naive solution, but works on for this problem.
Binary Search
Sorting makes it possible to do binary search. This can be solved in two steps, first we binary search to find the target row index, and second, we find the target in the target row. The complexity is O(logM + logN).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { auto rows = matrix.size(); if (rows == 0) return false; auto cols = matrix[0].size(); if (cols == 0) return false; int i = 0; int j = rows - 1; int mid; // find target row if (rows > 1) { while (i <= j) { mid = i + (j - i) / 2; if (target == matrix[mid][cols - 1]) { return true; } if (target > matrix[mid][cols - 1]) { i = mid + 1; } else { j = mid - 1; } } // comparing to the last element in the row rows = target > matrix[mid][cols - 1] ? mid + 1 : mid; } else { rows = 0; } if (rows >= matrix.size()) return false; i = 0; j = cols - 1; // binary search to find the target in the target row while (i <= j) { mid = i + (j - i) / 2; if (target == matrix[rows][mid]) { return true; } if (target > matrix[rows][mid]) { i = mid + 1; } else { j = mid - 1; } } return false; } }; |
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
auto rows = matrix.size();
if (rows == 0) return false;
auto cols = matrix[0].size();
if (cols == 0) return false;
int i = 0;
int j = rows - 1;
int mid;
// find target row
if (rows > 1) {
while (i <= j) {
mid = i + (j - i) / 2;
if (target == matrix[mid][cols - 1]) {
return true;
}
if (target > matrix[mid][cols - 1]) {
i = mid + 1;
} else {
j = mid - 1;
}
}
// comparing to the last element in the row
rows = target > matrix[mid][cols - 1] ? mid + 1 : mid;
} else {
rows = 0;
}
if (rows >= matrix.size()) return false;
i = 0;
j = cols - 1;
// binary search to find the target in the target row
while (i <= j) {
mid = i + (j - i) / 2;
if (target == matrix[rows][mid]) {
return true;
}
if (target > matrix[rows][mid]) {
i = mid + 1;
} else {
j = mid - 1;
}
}
return false;
}
};Moving Directions
If we start from the lowest-left element, each time move to right when the target is bigger or move upwards if the target is smaller. The function should return true when it meets the target or otherwise returns false when we step outside the matrix. The complexity is O(M + N).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { auto rows = matrix.size(); if (rows == 0) return false; auto cols = matrix[0].size(); if (cols == 0) return false; int i = rows - 1; int j = 0; while (i >= 0 && j < cols) { if (matrix[i][j] == target) return true; if (target > matrix[i][j]) { j ++; } else { i --; } } return false; } }; |
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
auto rows = matrix.size();
if (rows == 0) return false;
auto cols = matrix[0].size();
if (cols == 0) return false;
int i = rows - 1;
int j = 0;
while (i >= 0 && j < cols) {
if (matrix[i][j] == target) return true;
if (target > matrix[i][j]) {
j ++;
} else {
i --;
}
}
return false;
}
};- How to Search in 2D Sorted Matrix?
- https://helloacm.com/teaching-kids-programming-search-in-a-2d-sorted-matrix/
- GoLang: Search a 2D Matrix
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Tips For Keeping Your VPS Flawless
Next Post: All Steem Witnesses Should Now All Upgrade to 20.2 (Hardfork 20)