// Time Complexity : O(r * log(max - min) * logC)
import java.util.Arrays;
public class MedianInRowSorted
{
static public int matMed(int mat[][], int r ,int c)
{
int min = mat[0][0], max = mat[0][c-1];
for (int i=1; i<r; i++)
{
if (mat[i][0] < min)
min = mat[i][0];
if (mat[i][c-1] > max)
max = mat[i][c-1];
}
int medPos = (r * c + 1) / 2;
while (min < max)
{
int mid = (min + max) / 2;
int midPos = 0;
int pos = 0;
for (int i = 0; i < r; ++i){
pos = Arrays.binarySearch(mat[i],mid);
if(pos < 0)
pos = Math.abs(pos) - 1;
else
{
while(pos < mat[i].length && mat[i][pos] == mid)
pos += 1;
}
midPos = midPos + pos;
}
if (midPos < medPos)
min = mid + 1;
else
max = mid;
}
return min;
}
public static void main(String[] args)
{
int r = 3, c = 5;
int m[][]= { {5,10,20,30,40}, {1,2,3,4,6}, {11,13,15,17,19} };
System.out.println("Median is " + matMed(m, r, c));
}
}