Here, we will learn how to search an element in 2D sorted matrix by code and algorithm. We will solve it by using binary search.
You have to write an efficient algorithm that searches for a given value in an m * n
integer matrix 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.
Example 1:
1 | 6 | 9 | 10 |
11 | 12 | 16 | 20 |
23 | 30 | 40 | 60 |
Matrix: [[1, 6, 9, 10], [11, 12, 16,20], [23, 30, 40,60]] , Target: 9 Output: true Explanation: 9 is present in matrix at 0th row and 2nd column i.e matrix[0][2]
Example 2:
1 | 3 | 4 | 9 |
10 | 11 | 16 | 21 |
24 | 30 | 34 | 60 |
65 | 70 | 75 | 80 |
Matrix: [[1,3,4,9],[10,11,16,21],[24,30,34,60],[65,70,75,80]] Target: 15 Output: false Explanation: 15 is not present in matrix.
How to get row and column from index in matrix:
- row_index = index / column_size
- column_index. = index % column_size
Algorithm:
- Find the start point of matrix
- Find the end point of matrix i.e (m * n)
- Use binary search
- If value at middle index of matrix is equal to target then return true
- If value at middle index of matrix is less than target then update
start
point bymid + 1
- If value at middle index of matrix is greater than target then update end point by mid – 1
*** There are multiple ways to solve this problem
C++ code to search an element in sorted 2D matrix.
Code 1:
#include <iostream>
#include <vector>
using namespace std;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int start = 0, end = (row * col) - 1;
while(start <= end) {
int mid = (start + end) / 2;
int tmp_row = mid / col;
int tmp_col = mid % col;
if(matrix[tmp_row][tmp_col] == target) {
return true;
} else if(matrix[tmp_row][tmp_col] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}
int main()
{
vector<vector<int>> matrix = {
{1, 6, 9, 10},
{11, 12, 16, 20},
{23, 30, 40, 60}
};
int target = 9;
cout<<searchMatrix(matrix, target);
return 0;
}
Output: true Time complexity: O(log (m*n)) Space complexity: O(1) >>> There is no extra memory being used.
Code 2:
#include <iostream>
#include <vector>
using namespace std;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int i = m-1;
int j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target)
return true;
if (matrix[i][j] < target)
j++;
else
i--;
}
return false;
}
int main()
{
vector<vector<int>> matrix = {
{1, 6, 9, 10},
{11, 12, 16, 20},
{23, 30, 40, 60}
};
int target = 9;
cout<<searchMatrix(matrix, target);
return 0;
}
Output: true
Code 3:
#include <iostream>
#include <vector>
using namespace std;
bool search_ele(vector<int> arr, int i, int n, int target) {
while(i <= n) {
int mid = (i+n) / 2;
if(arr[mid] == target) {
return true;
}
if(arr[mid] < target) {
i = mid + 1;
} else {
n = mid - 1;
}
}
return false;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int size = matrix.size();
for(int i = 0; i < size; i++) {
int col_size = matrix[i].size();
if(matrix[i][0] < target && matrix[i][col_size-1] < target) {
continue;
} else {
return search_ele(matrix[i], 0, col_size-1, target);
}
}
return false;
}
int main()
{
vector<vector<int>> matrix = {
{1, 6, 9, 10},
{11, 12, 16, 20},
{23, 30, 40, 60}
};
int target = 100;
cout<<searchMatrix(matrix, target);
return 0;
}
Output: false
To check more leetcode problem’s solution. Pls click given below link:
https://techieindoor.com/category/leetcode/