[algogeeks] Re: Median of two sorted arrays of different sizes
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 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.
[algogeeks] Median of two sorted arrays of different sizes
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.
Re: [algogeeks]
//code sketch
row_len=R;
col_len=C;
r_start=0,col_start=0;
while (x < R*C)
{
for i=r_start to col_len
keep extracting value from 1D and add it to mat[r_start][i]=arr[p++];
r_start++;
for i=r_start to row_len
keep extracting value from 1D and add it to mat[i][col_len]=arr[p++];
col_len--;
for( i=col_len;i>=col_start;i--)
keep extracting value from 1D and add it to mat[row_len][i]=arr[p++];
row_len--;
for( i=row_len ; i >=r_start;i--)
keep extracting value from 1D and add it to
mat[i][col_start]=arr[p++];
col_start++;
}
keep on running above 4 loops till R*C times .
note : take care of 1D array bound , if all values are consumed then fill
with zero , add this checking in every loop.
On Thu, Apr 18, 2013 at 12:34 PM, w.s miller wrote:
> given a 1D array.The task is to convert it in to a 2D array and values
> should be filled spirally while filling from 1D array
>
> the size of 1D array is multiple of a constant say n.
> the number of rows and columns of 2D array will be given.
>
> say number of rows =R
> say number of columns = C
>
> k*n <= R*C. where k*n =number of elements in 1D array
> if (R*C > number of elements in 1D array)
> then rest of the values will be zeros.
> e.g.
>
> n=5; k=3
> R= 6
> C= 3
>
> input 1D array=[1,0,0,0,1,0,0,0,0,0,1,1,1,1,0]
>
> output 2D array
>
> 1 0 0 0 1 0
> 1 0 0 0 0 0
> 1 1 1 0 0 0
>
> here as 5*3<6*3 so ..18 -15 = 3
>
> i.e 3 remaining values are filled as zeros.
>
>
> --
> 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.
For more options, visit https://groups.google.com/groups/opt_out.
