find median with minimum time in an array

Question

I have an array lets say a = { 1,4,5,6,2,23,4,2}; now I have to find median of array position from 2 to 6 (odd total terms), so what I have done, I have taken a[1] to a[5] in arr[0] to arr[4] then I have sorted it and write the arr[2] as the median .

But here every time I put values from one array to another, so that the values of my initial array remains the same. Secondly, I have sorted, so this procedure is taking pretty much **time**. So I want to know if there is any way I can do this differently to reduce my computation time.

Any websites, material to understand, what, and how to do?

Solution 1

If you are doing multiple queries on the same array then you could use a Segment Tree. They are generally used to do range minimum/maximum and range sum queries but you can change it to do range median.

A segment tree for a set with n intervals uses O(n log n) storage and can be built in O(n log n) time. A range query can be done in O(log n).

Example of median in range segment tree:

You build the segment tree from the bottom up (update from the top down):

                    [5]
        [3]                     [7]
 [1,2]        [4]         [6]         [8] 
1     2     3     4     5     6     7     8

Indices covered by node:

                    [4]
        [2]                     [6]
 [0,1]        [3]         [5]         [7] 
0     1     2     3     4     5     6     7

A query for median for range indices of 4-6 would go down this path of values:

                    [4]
                          [5]
0     1     2     3     4     5     6     7

Doing a search for the median, you know the number of total elements in the query (3) and the median in that range would be the 2nd element (index 5). So you are essentially doing a search for the first node which contains that index which is node with values [1,2] (indices 0,1).

Doing a search of the median of the range 3-6 is a bit more complicated because you have to search for two indices (4,5) which happen to lie in the same node.

                    [4]
                                [6]
                          [5] 
0     1     2     3     4     5     6     7

Segment tree

Range minimum query on Segment Tree

Solution 2

Use std::nth_element from <algorithm> which is O(N):

nth_element(a, a + size / 2, a + size);
median = a[size/2];

Solution 3

It is possible to find the median without sorting in O(n) time; algorithms that do this are called selection algorithms.

Solution 4

To find the median of an array of less than 9 elements, I think the most efficient is to use a sort algorithm like insertion sort. The complexity is bad, but for such a small array because of the k in the complexity of better algorithms like quicksort, insertion sort is very efficient. Do your own benchmark but I can tell you will have better results with insertion sort than with shell sort or quicksort.

View more solutions

Comments

[Matthieu M.]

Note: this is a mutative algorithm, it might reorder some other items.

[Sudhanshu Gupta]

But because it distorts the array i have to make copies of array which i have to sort , its taking lots of time , what might i do to solve that

[ffao]

+1, this is the way to go if multiple queries are made on the same array.

[Chris A.]

Great answer. Just to clarify, the ones typically used (like in std::nth_element) are O(n) expected time, and not O(n) worst case time. The O(n) worst case time algorithm for this is typically slow in practice.

[Chris A.]

Update to my comment. Seems that there are tricks to achieve good practical running times and O(n) worst case running times. Would be nice to see which implementations use these.

[2147483647]

@ffao,justin, Can you tell more about how to do a range median query on a segment tree?

[Justin]

@A.06 I added an example of range minimum but it can easily be adapted to range median.

[2147483647]

But in the range minimum query, we can find minimum of multiple subranges and take the minimum among them, but I don't think it will be the same in the case of median because the median in a range will not necessarily be the median of the medians of its sub-ranges.

[Justin]

@A.06 I've added a median segment tree example.