3
$\begingroup$

I'm looking for a hint to help me think through/solve the problem of finding the median of two sorted lists/arrays in O(log(m+n)) time, where m,n are the sizes/lengths of each list, respectively.

I can immediately think of an obvious O(m+n) time algorithm using big-theta of m+n space, as follows: Merge the two lists into a new list in O(m+n) time. Find the middle element of that list in O(1) time (more particularly, if the merged list is even in length, take the mean of the floor of the element at index (m+n)/2, and the ceiling of the element at index (m+n)/2, otherwise the merged list length is odd and just use the element at (m+n)/2... potentially update logic for off-by-one depending on zero- or one-indexing).

But I don't immediately see how the median could be found in logarithmic time. Any hints would be appreciated!

$\endgroup$
2
$\begingroup$

Hint: Given any element, you can determine its relative position (in the sorted merged array) in time $O(\log m + \log n)$ using binary search. Use this primitive together with binary search to determine the median.

$\endgroup$
  • 1
    $\begingroup$ You have to be a little delicate in the analysis, though; at first glance this doesn't actually do better than $O(\log^2 n)$ running time (assuming that both lists are of size $n$), but the point is that the subsequent position-finding doesn't take 'full' time... $\endgroup$ – Steven Stadnicki Dec 12 '17 at 23:27
  • $\begingroup$ @StevenStadnicki I can't figure out how the complexity is not O(log m * log n) .. could you please point me in the right direction.. how is it O(logm + log n) $\endgroup$ – nilanjanaLodh Nov 14 at 23:09
  • $\begingroup$ @nilanjanaLodh are you wondering about the median algorithm itself or the 'merged position search'? $\endgroup$ – Steven Stadnicki Nov 14 at 23:27
2
$\begingroup$

Let say you have the two sorted array arrange as follow, using uppercase letter to represent a sequence of numbers and a lowercase letter to represent a single number:

[A,p,B] and [C,q,D]

Now suppose p > q, you know [A, p] and [C] > [q, D], then what can you do with this fact?

$\endgroup$

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.