Problem Statement
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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Sample Test Cases
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given target = 5, return true. Given target = 20, return false.
Problem Solution
The idea is to use Divide and Conquer approach to solve this problem.
So what we can do is search for the particular row in the matrix using the Binary Search technique, between which our element ‘K’ which to be searched may lie ie. matrix[i][0]<=K<=matrix[i][n-1].
Then we apply Simple binary search on that particular row to find whether ‘K’ is present in that row or not.
Complexity Analysis
Time Complexity: The time complexity of this algorithm will be O(log m+log n) because first, we will search for the particular row using binary search in O(log n) and then search for the element in that particular row in O(log m).
Space Complexity: O(1) no extra space is required .
Code Implementation
#include <bits/stdc++.h>
using namespace std;
#define M 5
#define N 5
// Basic binary search to
// find an element in a 1-D array
bool binarySearch1D(int arr[], int K)
{
int low = 0;
int high = N - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// if element found return true
if (arr[mid] == K)
return true;
// if middle less than K then
// skip the left part of the
// array else skip the right part
if (arr[mid] < K)
low = mid + 1;
else
high = mid - 1;
}
// if not found return false
return false;
}
// Function to search an element
// in a matrix based on
// Divide and conquer approach
bool searchMatrix(int matrix[M][N], int K)
{
int low = 0;
int high = M - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// if the element lies in the range
// of this row then call
// 1-D binary search on this row
if (K >= matrix[mid][0]
&& K <= matrix[mid][N - 1])
return binarySearch1D(matrix[mid], K);
// if the element is less then the
// starting element of that row then
// search in upper rows else search
// in the lower rows
if (K < matrix[mid][0])
high = mid - 1;
else
low = mid + 1;
}
// if not found
return false;
}
// Driver code
int main()
{
int matrix[M][N] = { {1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22},
{10, 13, 14, 17, 24},
{18, 21, 23, 26, 30} };
int K = 3;
if (searchMatrix(matrix, K))
cout << "Found" << endl;
else
cout << "Not found" << endl;
}
