Median

/*********************************************
X[1...n] and Y[1....n] are 2 sorted arrays....
give O(log n) algo to find median of the array
formed by merging the 2 arrays
*********************************************/

/***
Take the middle of Arr X call it midX and middle element of
Arr Y call it midY..
***/
int findMedian(Array arrX[])
{
lowX=0
lowY=0
highX=arrX.size - 1
highY=arrY.size - 1

midX = (highX - lowX)/2
midY = (highY - lowY)/2
while(lowX != highX || lowY !=highY)
{
if(midX < midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowX=midX
highY=midY
midX = midX + (highX - lowX)/2;
midY = (highY - lowY)/2;
**/
}
else if (midX > midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowY =midY
highX=midX
midY = midY + (highY - lowY)/2;
midX = (highX - lowX)/2;
**/
}
else
{
printf("median %d",arrX[midX]);
return arrX[midX];
}
}
return arrX[midX];/*or return arrY[midY]*/
}