Skip to content

Instantly share code, notes, and snippets.

@deyindra
Last active September 16, 2018 02:52
Show Gist options
  • Save deyindra/6821852c3ba43af98d2b24a35d90d5be to your computer and use it in GitHub Desktop.
Save deyindra/6821852c3ba43af98d2b24a35d90d5be to your computer and use it in GitHub Desktop.
Median of 2 sorted array of different length
public static double findMedian(int[] input1, int[] input2){
if(input1.length>input2.length){
return findMedian(input2,input1);
}
int x = input1.length;
int y = input2.length;
int low = 0;
int high = x;
while (low <= high){
int partitionX = (low + high)/2;
int partitionY = (x+y+1)/2 - partitionX;
int maxLeftX = (partitionX==0) ? Integer.MIN_VALUE : input1[partitionX-1];
int minRightX = (partitionX == x) ? Integer.MAX_VALUE : input1[partitionX];
int maxLeftY = (partitionY==0) ? Integer.MIN_VALUE : input2[partitionY-1];
int minRightY = (partitionY == y) ? Integer.MAX_VALUE : input2[partitionY];
if(maxLeftX<=minRightY && maxLeftY<=minRightX){
if((x+y)%2==0){
return (double)(Math.max(maxLeftX,maxLeftY) + Math.min(minRightX,minRightY))/2;
}else{
return (double)(Math.max(maxLeftX,maxLeftY));
}
}else if(maxLeftX>minRightY){
high = partitionX -1;
}else{
low = partitionX + 1;
}
}
throw new IllegalArgumentException();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment