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].
So 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
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ePBMAl0aP4cJ.
To post to this
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
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;
see this link
http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-in-union-of.html
regards
Shyam
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from
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)
{
I think that the complexity might even be log(sizeA) where A is the
smaller of the two arrays.
Imagine that you have sizeA = 3 and sizeB = 1,000,000,000.
You know that the median will either be in A, or it will be
B[500,000,000+/-1].
The binary search will start off by comparing A[1] with
On Fri, Sep 2, 2011 at 2:09 AM, Don dondod...@gmail.com wrote:
I think that the complexity might even be log(sizeA) where A is the
smaller of the two arrays.
Imagine that you have sizeA = 3 and sizeB = 1,000,000,000.
You know that the median will either be in A, or it will be
