My O(ln n) binary search solution does not merge them.
In C code, it looks something like this:
// 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, 1:01 pm, Rahul Verma <[email protected]> wrote:
> how we find the median, if we don't have sufficient memory to merge them.
--
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.
