Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient code to find median.
int median(int a[], int b[], int n)
{
int med1,med2;
if(a[n1] < b[0])
return a[n1];
if(b[n1] < a[0])
return b[n1];
if(n==2)
{
int c[4];
merge(a,b,c,2);
return c[1];
}
med1 = a[(n1)/2];
med2 = b[(n1)/2];
if(med1 == med2)
return med1;
else if(med1 < med 2)
return median(&a[(n1)/2],b,n/2+1);
else
return median(a,&b[(n1)/2],n/2+1);
}
where “a” and “b” are 2 sorted arrays and n is size…
i hope this may help
The problem can be solved in a linear O(N) time ,where N is the Dimension of Matrix ,[if the matrix is Non Square Matrix ,then N=max (row,col)].
The Matrix in which Every row and Every columns are sorted is called YOUNG TABLEAU.
This 2 D matrix or Tableau behaves as a Heap from one End and Binary search Tree from another End.
This blog explains the approach ::
Lets name the matrix A of size N x N
Take any element A[i][j]
1. A[i][j] < A[t][j] for t = i+1 ....... N
2. A[i][j] < A[i][t] for t = j+1 ....... N
3. A[i+1][j] and A[i][j+1] can be thought of as childs of A[i][j]
thus above structure resembles a heap
similarly from upper right corner the matrix looks like a BST
do insert operation in BST > O(n) in this case
do search operation in HEAP > O(n) in this case
we can also do this by heap 

creating min heap and keep the row and column also
struct heap
{
int val, row , col
}*h; 
do following (n*n)/2 times
2a. now remove the min element & check its column number and insert into heap the next number from the
same column like
matrix[removedelementrow+1][removedelementcolumn] will be the new element … insert it
2b. call min heapify on root
3.return the last extracted root