2
$\begingroup$

If there are given two arrays, A and B, each containing n real numbers in sorted order. How to compute the median of all the numbers in A and B, in O(log n) time. I have to make an algorithm that takes at most logarithmic time.

My idea:

A = 1, 3, 6, 8, 10, 15, 20

B = 1, 2, 3, 7, 10, 30

C = sort(A, B)

a = len(A) // 7
b = len(B) // 6
M = (a+b)/2 // 6.5
if M is a fraction:
    Median = C[M+0.5]
else:
    Median = (C[M]+C[M+1])/2

How to write sort function under complexity O(log n)? I don't even have to sort all the elements of A and B, I only need the first M+1 elements of C because of above method.

$\endgroup$
  • 1
    $\begingroup$ You cannot sort $n$ numbers in time less than $n$. Try another approach that does not require sorting. Start from finding median of the both arrays and finding them in the opposite arrays (median of $A$ in the array $B$ and the median of $B$ in the array $A$). Think what would be the next step. $\endgroup$ – Evil Feb 5 '17 at 3:58
  • $\begingroup$ @Evil Thanks for answering. In the above example median of A is 8 and B is 10 [(3+7)/2]. 8 is not present in B and 10 is present in A. However, actual median is 7, which is not even between 8 and 10. Please help! $\endgroup$ – New_Coder Feb 5 '17 at 4:20
  • $\begingroup$ The median of $B$ is $5$, since you take $\frac{a+b}{2}$, so your median is between 5 and 8, so far so good. How can you use the new obtained info that median is in this range? $\endgroup$ – Evil Feb 5 '17 at 4:27
  • $\begingroup$ List all the elements in both the arrays between 5 and 8 is 6, 7, 8 and 7 is the median of both the arrays. Does that mean median will be the middle element of all the elements between the range (median of A and B)? $\endgroup$ – New_Coder Feb 5 '17 at 4:43
  • $\begingroup$ @Evil Do you think, the median of both the arrays will be the average of medians of A and B. In above example, medians of A and B are 8 and 5. Its average is (8+5)/2=6.5, but the median should be 7. So, median will be celling of 6.5 that is 7. Is that correct? $\endgroup$ – New_Coder Feb 5 '17 at 13:54
2
$\begingroup$

There are two arrays: $A, B$ with lengths $n, m$. Finding median in the sorted array takes constant time (just access middle element or take a mean of two center elements).

To find the median of all elements in $\mathcal O(min(\log n, \log m))$ perform the following steps:

  1. If $(length(A) \le 2$ or $length(B) \le 2)$ or $(A _{last} \le B_{first}$ or $B_{last} \le A_{first})$ calculate median and return.

  2. Set $A_m = median(A), B_m = median(B)$ and compare them. If $A_m = B_m$ return result. If $A_m < B_m$ then discard first half of $A$ and the same amount of elements from the second half of $B$. else if $A_m > B_m$ then discard second half of $A$ and the same amount of elements from the first half of $B$.

  3. Goto 1

This algorithm runs in logarithmic time. Minimum in the complexity reflects the fact that when the smaller array has length $\le 2$ the procedure terminates. At step 2 the both arrays get halved (or procedure is terminated) so it will be performed at most $\log_2(min(n, m))$ times.

By calculate median there are two cases: at least one arrays length was $\le 2$, so shift the median of the second array accordingly, or arrays do not overlap (or share the boundary element) then the median is the center element of two arrays concatenated in ascending order. In fact only index is calculated, no actual concatenation takes place.

Why the procedure stops when at least one of lengths is $\le 2$? Consider the corner case, e.g. A = [2, 9], B = [3, 11], the median is 6, but taking them separately yields 5.5 and 7, which in turn yields incorrect result 6.25.

For example:
$A = [1, 2, 6, 8, 12, 15], B = [2, 5, 8, 15]$ to keep an overview, the whole sorted array $C = [1, 2, 2, 5, 6, 8, 8, 12, 15, 15], C_m = 7$.
$A_m = 7, B_m = 6.5$ now $A_m > B_m$ so we drop [12, 15] from $A$ and we drop [2, 5] from $B$. Why $8$ is not dropped from $A$? Bacause we cannot drop $8$ from $B$, and in order to preserve median we can only drop the same number of elements ftom the both arrays at the opposite sites of the mean.
So $A = [1, 2, 6, 8], B = [8, 15]$. Now back to step 1, the arrays do overlap by common element at the end so we take $AB$, the lengths are 4, 2, so it is a mean of 3rd and 4th element $\frac{6 + 8}{2} = 7$.

$\endgroup$
  • $\begingroup$ Thank you so much for your answer. I am confused that in step 1, we have to calculate median of A or B? I tried your algorithm with an example, but not sure it works: A = 1, 2, 6, 8, 12, 15 B = 2, 5, 8, 15 1. Condition fails 2. Am = 7, Bm = 6.5 Am>Bm, so A = 1, 2, 6 and B = 15 1. (length(A)≤2 or length(B)≤2) ==> (3≤2 or 1≤2) ??? What to do here to get the median (that is 7) $\endgroup$ – New_Coder Feb 6 '17 at 0:30
  • $\begingroup$ The algorithm says that discard first half of A, so I made A = 1, 2, 6. It's not clear why it should be A=[1,2,6,8]. Why we cannot drop 8 from B and A? $\endgroup$ – New_Coder Feb 6 '17 at 2:20
  • 1
    $\begingroup$ Ok, I should have wrote "part" instead of half. Half works for arrays of the same size, but your examples were different, so I adjusted accordingly. Imagine some point where the both median are. The median of all elements (7 from the example) is somwhere between 6.5 and 7, but we do not know where, so if we do not want to change the median we can't move anything inside that interval and can't drop different number of elements on the both sides because it influences the median. I have added constraint about it, so we drop minimum of possible number of elements from the both ends $\endgroup$ – Evil Feb 6 '17 at 2:36
  • $\begingroup$ A = [1,2,6,8,12,15], its median is 7. Why discarding second part of A will make it A=[1,2,6,8] and not A=[1,2,6]? $\endgroup$ – New_Coder Feb 6 '17 at 3:56
  • 2
    $\begingroup$ Because you cannot discard 3 numbers from B. It is constrained like this. $\endgroup$ – Evil Feb 6 '17 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.