here is pseudo code on algorithm to find median of two array
T WO -A RRAY-M EDIAN (X, Y )
n ← length[X] £ n also equals length[Y ]
median ← F IND -M EDIAN (X, Y, n, 1, n)
if median = NOT- FOUND
then median ← F IND -M EDIAN (Y, X, n, 1, n)
return median
F IND -M EDIAN ( A, B, n, low, high)
if low > high
then return NOT- FOUND
else k ← (low + high)/2
if k = n and A[n] ≤ B[1]
then return A[n]
elseif k < n and B[n − k] ≤ A[k] ≤ B[n − k + 1]
then return A[k]
elseif A[k] > B[n − k + 1]
then return F IND -M EDIAN ( A, B, n, low, k − 1)
else return F IND -M EDIAN ( A, B, n, k + 1, high)
it is from introduction of algorithms MIT
and here is my code please if something is wrong in my code tell me
publi开发者_如何学编程c class findmedian{
public static int find(int []x,int []y){
int median;
int n=x.length;
median=Median( x, y, n,0, n);
if ( median<-100000){
Median(y,x, n,1, n);
}
return median;
}
public static void main(String[]args){
int x[]=new int[]{3,5,7,8,5,9,10};
int y[]=new int[]{12,4,8,9,6,7,10};
find(x,y);
}
public static int Median(int []a,int []b,int n,int low,int high)
{
if ( low>high)
return -1 ;
int k=(low+high)/2;
if (k==n && a[n]<=b[1])
return a[n];
else if ( k<n && b[n-k]<=a[k] && b[n-k]<=b[n-k+1])
return a[k];
else if ( a[k]> b[n-k-1])
return Median( a,b,n,low,k-1);
return Median(a,b,n,k+1,high);
}
}
after compile it does not return anything please help
if ( low>high)
return;
Is this the error? You need to return something. (The return type is int)
精彩评论