Parallel
Finding the Median of Two Sorted Arrays Efficiently
Merge operations integrate sorted arrays by triaging entries based on a median value. Finding that value accurately and efficiently requires careful work.Related Reading
More Insights
INFO-LINK
To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy. | |
Comments:
2016-07-26T12:56:03
How is the unoptimized algorithm O(log (n+m))? There are essentially two binary searches, with a complexity of log(n) and log(m), respectively. The sum is log(n)+log(m) = log(n*m). Thus, it seems to me the total complexity should be O(log (n*m)). Am I missing something?
Permalink
2014-10-30T19:07:11
It's the median value, not the median unique value; which means it's 1, not 2.
Permalink
2014-10-30T12:17:42
Median is defined as the value that is in the physically/positionally middle of a sorted array. In your example, the median would be a 1, the a[5] element, with five 1's to the left of it and 1,1,1,2,3 to the right of it, since there are 11 elements total.
Permalink
2014-10-30T06:27:10
does the algorithm work for duplicated number like the following?
1 1 1 1 1 1 1 1 1 2 3 (first 9 numbers are 1, and the last two are 2 and 3), the median value should be 2, right?
Permalink
2014-10-29T12:23:23
Thank you for pointing out the 3 mistakes. We'll correct these shortly.
For the M/2 question, it's integer division. In this case precision is not critical. For algorithm analysis most of the time M is very large, and would be more precise to say "about M/2 elements".
Permalink
2014-10-28T21:29:37
I started to read this article, because it sounded so interesting, but I can't finish. The author either has very limited attention to detail, or nobody reviewed/edited this before publishing. The text contains so many mistakes, that my tiny little brain is expending all its energy trying to decide if what I'm reading is correct and I just don't understand, or whether the explanation is just wrong.
Example (the paragraph immediately after Figure 1): "The value of X is used in the binary search to find an index where all elements to the RIGHT are SMALLER than X."
Example: "Also, 11 elements are larger or equal to X: 6 from the LEFT BLOCK and 5 from the LEFT BLOCK." And really? Only 6 from the left block ... shouldn't it be 7 ... why are you not counting X itself? Wouldn't X be considered "larger or equal to X"?
Example: "For instance, if both blocks have M elements, and M is odd, then within the left block, M/2 elements will be smaller than or equal to X, and M/2 elements will be greater than or equal X." How is that possible? If M is 5, then M/2 is 2.5. Or, if you're doing integer division, then just 2. Either way, it's wrong because there are actually 3 elements that are smaller or equal to X, and 3 elements that are larger or equal to X.
Example: "It's possible to do better than O(N), by using a MODIFIED BINARY leading to O(lgN) performance." What's a "modified binary"?
Permalink
2014-10-28T19:39:18
You are both absolutely right, sorry about that, and the fault was mine entirely in processing Victor's submitted figures. The images are now fixed to appear as they were intended.
Permalink
2014-10-28T19:23:17
The images display Ok, it's the content that is problematic. In Figure 1 the points of interest are labeled left to right as X, l, r, m. From the text they should be l, X, m, r.
Figure 2 is described as "Figure 2 shows two sorted arrays on the top line, in which an overall
median is to be found. On the lower line, the two arrays have been
merged into a single sorted array with the median shown, as the
mid-element at offset 4 labeled with an M." But the upper right array in the image is sorted backwards, the lower array is unsorted, and there are numbers in the image that are not explained and don't seem to fit. This seems to be an image related to the problem but not the one described.
Permalink
2014-10-28T18:02:11
How so? (They are displaying OK on my screen)
Permalink
2014-10-28T17:03:14
I believe the gifs are messed up
Permalink