2
$\begingroup$

If array is sorted we can generally find median in O(1) by returning the element at the middle. But what if there are duplicates?

E.g [2, 2, 3, 3, 3, 3]

$\endgroup$
2
  • 2
    $\begingroup$ The same. And when the length is even there are various definitions: return mean of teo middle elements or the lower (upper) one to keep median as element of the set. There is no definition depending on elements in the array. $\endgroup$
    – Evil
    Commented Oct 19, 2016 at 23:47
  • 2
    $\begingroup$ Now, if you wanted median(set(input)), rather than median(input), then things would be significantly harder. ​ ​ $\endgroup$
    – user12859
    Commented Oct 20, 2016 at 3:11

1 Answer 1

2
$\begingroup$

Yes. Even with duplicates, the process of finding median is same. See this link - https://math.stackexchange.com/questions/1191119/how-to-find-the-median-of-three-numbers-if-one-of-them-appears-twice

$\endgroup$
1
  • 1
    $\begingroup$ How does that link help answering the question? $\endgroup$
    – Raphael
    Commented Oct 20, 2016 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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