1
$\begingroup$

What is the most effective way of finding median from $N$ numbers within given range ? It is guaranted that $N \leq 10^{9}$.

The input consists of $L$ lines.

Each line consists either of:

a) S X , which means store number $X$, where $X \leq 10^{9}$.

or

b)F X Y, which means find median from stored numbers within range $(X,Y)$. where $1 \leq X,Y \leq 10^{9}$

For each F X Y ( median range request ) it should print the median from all stored numbers within range $(X, Y)$

Example:

Suppose the input:

S 20
S 10
S 22
S 30
S 25
F 21 30
S 5
S 7
S 9
F 5 20

Output:

   Median from range (21, 30) : 25
   Median from range (5, 20) : 9

Explanation:

The first median request for range (21, 30) satisfie 3 numbers: 22 25 30 where the median is 25.

The second median request for range (5, 20) satisfie 5 numbers: 5, 7, 9, 10, 20 and we pick up the median which is 9.

The mean is not guaranted to be close to median. The requests for storing S do not have to go consecutevly.

$\endgroup$
  • $\begingroup$ The input consists of N random numbers ( unsorted ) which you store. Then there go requests for median range calculation which for each request print the median within the range. There is not guarantee that mean is near median. $\endgroup$ – kvway Nov 4 '17 at 20:53
  • 1
    $\begingroup$ @Evil I edited my question entirely since another numbers for storing can come after median request. So u would have to sort the array many times which would be slow. $\endgroup$ – kvway Nov 4 '17 at 21:46
  • 1
    $\begingroup$ Could you credit the sources? Where have you encountered this task? $\endgroup$ – Evil Nov 4 '17 at 22:21
1
$\begingroup$

It can be done in $O(L \log L)$ time, which is optimal by reduction from sorting.

Consider a Red-Black Tree $T$ (or any other self-balancing tree) where each node $v$ is augmented with $s(v)$, the number of nodes in the subtree rooted in $v$. Keeping such information updated between insertions is trivial.

In order to show that such structure supports median queries in $\log L$ time, it is sufficient to show that we can perform the following operations in $\log |T|$ time:

  • Given $v \in T$, determine $\#v$.

  • Given $n \in \mathbb{N}$, find $v \in T$ such that $\#v = n$.

To solve the first problem, initialize a variable $x := 0$ and then find $v$. Whenever in the search you are located at a node $w$, if you move right, it means that $v$ is higher than $w$ and each node in the left child of $w$. In such a case, we set $x := x + s(w.left) + 1$. When we reach $v$, we similarly set $x := x + (v.left) + 1$.

After that last update, it will hold $x = \#v$, that is true because $v$ is the minimum of the tree $T_L$ obtained starting from $T$ and cutting the left branch every time you moved to the right while searching $v$, and, conversely, the maximum of the analogous $T_R$.

The second problem can be solved by a similar idea: initialize $x:=0$ to keep track of how many elements you "discarded" by going right, and then perform a dichotomic search.

$\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.