Re: [algogeeks] Re: Median of two sorted arrays of different sizes
How is this code dealing with the scenario where two arrays have common
number. For example where two arrays are same. A[] = {1,2,3,4} and B[] =
{1,2,3,4}. Here the median position is not (4+4)/2 rather it is 4/2.
On Sun, Jun 9, 2013 at 3:12 PM, rahul sharma rahul23111...@gmail.comwrote:
@doncan u plz explain the approach used.I didnt get this.
On 4/25/13, Don dondod...@gmail.com wrote:
Let's say you have two arrays: A[x] and B[y].
The median is the (x+y)/2th value.
If A[i] is the median, then B[(x+y)/2-i] = A[i] and B[(x+y)/2-i+1] =
A[i].
You can use a binary search to find the point where that condition
occurs. Of course you want to search on the smaller array.
You'll need some logic at the end to determine if the median is in A
or in B.
// Input arrays A and B, sizeA = sizeB
int A[sizeA];
int B[sizeB];
int min = 0;
int max = sizeA;
const int medianPos = (sizeA + sizeB) / 2;
while(max = min)
{
i = (min + max) / 2;
j = medianPos-i;
if (B[j] A[i]) min = i+1;
else if (B[j+1] A[i]) max = i-1;
else break;
}
printf(Median is %d\n, (A[i] B[j]) ? A[i] : B[j]);
Don
On Apr 24, 1:19 pm, rahul sharma rahul23111...@gmail.com wrote:
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.
--
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,
Re: [algogeeks] Re: Median of two sorted arrays of different sizes
@doncan u plz explain the approach used.I didnt get this.
On 4/25/13, Don dondod...@gmail.com wrote:
Let's say you have two arrays: A[x] and B[y].
The median is the (x+y)/2th value.
If A[i] is the median, then B[(x+y)/2-i] = A[i] and B[(x+y)/2-i+1] =
A[i].
You can use a binary search to find the point where that condition
occurs. Of course you want to search on the smaller array.
You'll need some logic at the end to determine if the median is in A
or in B.
// Input arrays A and B, sizeA = sizeB
int A[sizeA];
int B[sizeB];
int min = 0;
int max = sizeA;
const int medianPos = (sizeA + sizeB) / 2;
while(max = min)
{
i = (min + max) / 2;
j = medianPos-i;
if (B[j] A[i]) min = i+1;
else if (B[j+1] A[i]) max = i-1;
else break;
}
printf(Median is %d\n, (A[i] B[j]) ? A[i] : B[j]);
Don
On Apr 24, 1:19 pm, rahul sharma rahul23111...@gmail.com wrote:
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.
--
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.
