Find median in row wise sorted matrix in C++

In this tutorial, we are about to learn about Find median in a row-wise sorted matrix in C++. Firstly an introduction to the matrix is given. Secondly, we will discuss the algorithm we will use to solve the problem.

Introduction to matrix and median

Matrix or 2-D array is a data structure in which we can store the data in rows and columns. For the iteration of the matrix, we need two loops which make the insertion in the matrix a bit expensive. But matrix has so much implementation in programming that it is still used.

Median of a matrix is the middle element of the sorted matrix. In this problem, we are provided with a sorted matrix we just have to find the median.

There are two ways to solve this problem:

  1. First, one to create an array and transfer the data into that array and pick the middle element. But it takes extra space of the array.
  2. The second way is to use the algorithm of binary search and find n/2 elements less than one element and it is the median.

In this tutorial, we are going to use the second method.

Program to find median in row wise sorted matrix in C++

#include<bits/stdc++.h> 
using namespace std; 
  
const int MAX = 100; 
  
int med(int m[][MAX], int r ,int c) 
{ 
    int min = INT_MAX, max = INT_MIN; 
    for (int i=0; i<r; i++) 
    { 
        if (m[i][0] < min) 
            min = m[i][0]; 
  
        if (m[i][c-1] > max) 
            max = m[i][c-1]; 
    } 
  
    int desire = (r * c + 1) / 2; 
    while (min < max) 
    { 
        int mid = min +(max-min)/2; 
        int place = 0; 
   
        for (int x=0; x<c; x++) 
            place += upper_bound(m[x], m[x]+c, mid) - m[x]; 
        if (place < desire) 
            min = mid + 1; 
        else
            max = mid; 
    } 
    return min; 
} 
  
int main() 
{ 
    int size;
    cout<<"Enter the size of matrix : ";
    cin>>size;
    int m[MAX][MAX];
    for(int i=0;i<size;i++){
    	for(int j=0;j<size;j++){
    		cin>>m[i][j];
    }
  }
    cout << "Median of matrix is " << med(m,size,size) << endl; 
    return 0; 
}

Input and Output:

Enter the size of matrix : 3
1 2 3
4 5 6
3 8 9
Median of matrix is 4

In the above code first, we have taken values into the matrix which are row-wise sorted. Then function med is called with arguments matrix and the size. It returns the value of the median.

Conclusion

Finally, this program uses the concept of matrix and binary searching. This can also be used in problems like searching in a matrix. This is the tutorial on Find median in row-wise sorted matrix in C++.

Also Checkout:

Heap Sort in C++
Finding Minimum Cost Path in a 2-D Matrix in C++
How to find product of given two matrices in C++

Leave a Reply

Your email address will not be published. Required fields are marked *