# 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:

- 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.
- 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