IS this code correct?
float findMedianUtil( int A[], int N, int B[], int M )
{
// If the smaller array has only one element
if( N == 1 )
{
// Case 1: If the larger array also has one element, simply call MO2()
if( M == 1 )
return MO2( A[0], B[0] );
// Case 2: If the larger array has odd number of elements, then consider
// the middle 3 elements of larger array and the only element of
// smaller array. Take few examples like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if( M & 1 )
return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );
// Case 3: If the larger array has even number of element, then median
// will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3( B[M/2], B[M/2 - 1], A[0] );
}
// If the smaller array has two elements
else if( N == 2 )
{
// Case 4: If the larger array also has two elements, simply call MO4()
if( M == 2 )
return MO4( A[0], A[1], B[0], B[1] );
// Case 5: If the larger array has odd number of elements, then median
// will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element just
// before the middle in bigger array
// 3. Min of second element of smaller array and element just
// after the middle in bigger array
if( M & 1 )
return MO3 ( B[M/2],
max( A[0], B[M/2 - 1] ),
min( A[1], B[M/2 + 1] )
);
// Case 6: If the larger array has even number of elements, then
// median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4 ( B[M/2],
B[M/2 - 1],
max( A[0], B[M/2 - 2] ),
min( A[1], B[M/2 + 1] )
);
}
int idxA = ( N - 1 ) / 2;
int idxB = ( M - 1 ) / 2;
/* if A[idxA] <= B[idxB], then median must exist in
A[idxA....] and B[....idxB] */
if( A[idxA] <= B[idxB] )
return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
/* if A[idxA] > B[idxB], then median must exist in
A[...idxA] and B[idxB....] */
return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
}
In the end I suspect the following part:-
if( A[idxA] <= B[idxB] )
return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
/* if A[idxA] > B[idxB], then median must exist in
A[...idxA] and B[idxB....] */
return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
plz comment
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
