Searching a number in a 2D Sorted Matrix
Given : 2 dimensional sorted matrix.
- The numbers in each row are sorted in ascending order.
- The first number in each row is greater than the last number in the previous row.
Task : Check if a number exists in the given 2D matrix.
Solution :
- To solve this problem, we would treat the 2-dimensional array as a 1-dimensional array, as we can see in the image below.
- Since we still have to search the element in the 2-d array, we would need the row and the column.
- Row would be the value of ( mid / the number of columns ) in the 2-d array. Example: If mid == 5, then to find the number at index mid, the row number would be 5 / 4 i.e row number 1.
- Column would be ( mid - ( row * number of columns ) ) i.e 5 - ( 1 * 4 ) = 1.
- Thus we would check if array [ 1 ] [ 1 ] has the number that we are searching for.
Time complexity : Log ( N ), where N is the number of elements in the given 2D matrix.
Why is mid calculated as mid = beg + (end-beg)/2 ?
Integer range is -2,147,483,648 to 2,147,483,647. If you are searching in an array of size 2,000,000,000 and the element searched for is located at index 1,999,999,999. When you search in the upper half of array, beg=1,000,000,001 and end=2,000,000,000. If mid is calculated as (low+high)/2, low+high = 3,000,000,001; which exceeds the range of int, resulting in overflow errors. But mid calculated as beg + (end-beg) = 1,000,000,001 + 999,999,999 = 2,000,000,000; which fits in the integer range.
Program to find a number in a 2D sorted matrix using Binary Search
#include<iostream>
#include<vector>
using namespace std;
bool SearchMatrix (vector<vector<int>>& matrix, int target) {
int beg = 0;
int end = matrix[0].size() * matrix.size() - 1;
int factor = matrix[0].size();
while (beg <= end) {
int mid = beg + (end - beg)/2;
int row = mid / factor;
int col = mid - (row * factor);
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
end = mid-1;
} else {
beg = mid+1;
}
}
return false;
}
int main() {
vector<vector<int>> mat = {{2, 4, 5, 8},
{10, 12, 18, 20},
{24, 31, 37, 60}};
cout << "Matrix" << endl;
for (auto& vec : mat) {
for (auto& num: vec) {
cout << num << " ";
} cout << endl;
}
vector<int> targets = {2, 3, 11, 25, 24, 60};
for (auto& target : targets) {
cout << "\nSearching for " << target << ". ";
if (SearchMatrix(mat, target)) {
cout << "Found." << endl;
} else {
cout << "Not found." << endl;
}
}
return 0;
}
Output
Matrix
2 4 5 8
10 12 18 20
24 31 37 60
Searching for 2. Found.
Searching for 3. Not found.
Searching for 11. Not found.
Searching for 25. Not found.
Searching for 24. Found.
Searching for 60. Found.
def SearchMatrix (matrix, target) :
beg = 0
end = len(matrix[0]) * len(matrix) - 1
factor = len(matrix[0]) # Number of columns in the 2-D array
while (beg <= end) :
mid = beg + int((end - beg) / 2)
row = int(mid / factor)
col = int(mid - (row * factor))
if matrix[row][col] == target :
return True
elif matrix[row][col] > target :
end = mid - 1
else :
beg = mid + 1
return False
def main() :
mat = [[2, 4, 5, 8],
[10, 12, 18, 20],
[24, 31, 37, 60]]
print("Matrix")
for row in mat :
print(row)
targets = [2, 4, 36, 37, 21, 60]
for target in targets:
print("\nSearching for " + str(target) + ".", end = " ")
if SearchMatrix(mat, target) :
print("Found !!")
else :
print("Not found !!")
if __name__ == "__main__" :
main()
Output
Matrix
[2, 4, 5, 8]
[10, 12, 18, 20]
[24, 31, 37, 60]
Searching for 2. Found !!
Searching for 4. Found !!
Searching for 36. Not found !!
Searching for 37. Found !!
Searching for 21. Not found !!
Searching for 60. Found !!
class BinarySearch {
boolean SearchMatrix (int[][] matrix, int target) {
int beg = 0;
int end = matrix[0].length * matrix.length - 1;
int factor = matrix[0].length;
while (beg <= end) {
int mid = beg + (end - beg)/2;
int row = mid / factor;
int col = mid - (row * factor);
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
end = mid-1;
} else {
beg = mid+1;
}
}
return false;
}
public static void main (String[] args) {
int[][] mat = {{2, 4, 5, 8},
{10, 12, 18, 20},
{24, 31, 37, 60}};
BinarySearch s = new BinarySearch();
System.out.println("Matrix");
for (int row = 0; row < mat.length; row++) {
for (int col = 0; col < mat[0].length; col++) {
System.out.print(mat[row][col] + " ");
} System.out.println();
}
int[] targets = {2, 13, 37, 25, 24, 60};
for (int i = 0; i < targets.length; i++) {
System.out.print("\nSearching for " + targets[i] + ". ");
if (s.SearchMatrix(mat, targets[i])) {
System.out.println("Found !!");
} else {
System.out.println("Not found !!");
}
}
}
}
Output
Matrix
2 4 5 8
10 12 18 20
24 31 37 60
Searching for 2. Found !!
Searching for 13. Not found !!
Searching for 37. Found !!
Searching for 25. Not found !!
Searching for 24. Found !!
Searching for 60. Found !!