Searching a number in a 2D Sorted Matrix
Given : 2 dimensional sorted matrix.
- The numbers in each row are sorted from left to right.
- The first number in each row is greater than the last number in the previous row.
Task : Efficiently check if a number exists in the given 2D matrix.
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;
}
int target = 4;
cout << "\nSearching for " << target << ". ";
if (SearchMatrix(mat, target)) {
cout << "Found" << endl;
}
target = 36;
cout << "Searching 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 4. Found
Searching for 36. Not found.