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.com>wrote:
> @don....can 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.
>
>
>
--
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.
