Hi Don,
Your algorithm is correct! I guess it can be simplified and made easy to
understand as follows:
Idea is to reduce the size of elements under consideration by half in each
iteration.
int aStart = 0, aEnd = sizeA;
int bStart = 0 , bEnd = sizeB;
while(aStart < aEnd || bStart < bEnd)
{
aMid = (aStart + aEnd) / 2;
bMid = (bStart + bEnd) / 2;
if(a[aMid] > b[bMid])
{
aEnd = aMid;
bStart = bMid;
}
else
{
aStart = aMid;
bEnd = bMid;
}
printf("Median is %d\n", (A[aMid] > B[bMid]) ? A[i] : B[j]);
}
I think this will give the answer, and the complexity is surely log(sizeA +
sizeB).
On Thu, Sep 1, 2011 at 11:55 PM, Don <[email protected]> wrote:
> My O(ln n) binary search solution does not merge them.
> In C code, it looks something like this:
>
> // 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 Sep 1, 10:31 am, Ankur Garg <[email protected]> wrote:
> > Can anybody explain logic ?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Regards,
-Jay Mahadeokar
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
