32
\$\begingroup\$

Challenge

Given a nonempty list of real numbers, compute its median.

Definitions

The median is computed as follows: First sort the list,

  • if the number of entries is odd, the median is the value in the center of the sorted list,
  • otherwise the median is the arithmetic mean of the two values closest to the center of the sorted list.

Examples

[1,2,3,4,5,6,7,8,9] -> 5
[1,4,3,2] -> 2.5
[1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4] -> 1.5
[1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4] -> 1.5
\$\endgroup\$
  • \$\begingroup\$ Can we output as a fraction over 2 (e.g. 7/2 or 8/2) \$\endgroup\$ – Wheat Wizard Jan 8 '17 at 23:34
  • \$\begingroup\$ According to this fractions are fine. \$\endgroup\$ – flawr Jan 8 '17 at 23:36
  • 15
    \$\begingroup\$ How is this not already a challenge? \$\endgroup\$ – orlp Jan 8 '17 at 23:53
  • 1
    \$\begingroup\$ @orlp This is a subset of this challenge. \$\endgroup\$ – AdmBorkBork Jan 9 '17 at 17:44
  • 3
    \$\begingroup\$ It's also makes a nice fastest code challenge as there are some interesting linear time algorithms. \$\endgroup\$ – user9206 Jan 10 '17 at 10:51

54 Answers 54

1
2
2
\$\begingroup\$

Python 3, 59 bytes

f=lambda l:l.sort()or(len(l)<3)*(l[0]+l[-1])/2or f(l[1:-1])

Try it online!

This is a recursive version:

  • the list is sorted
  • if there are 1 or 2 elements left, we output the median since 0 and -1 are both first and last with a single or atwo element list
  • if not, we remove first and last elements and call f.
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Racket 113 bytes

(let*((L(sort L >))(n(length L))(r list-ref))(if(odd? n)(r L(floor(/ n 2)))(/(+(r L(-(/ n 2)1))(r L(/ n 2)))2)))

Ungolfed:

(define (median L)
  (let* ((L (sort L >))
         (n (length L))
         (lr list-ref))
    (if (odd? n)
        (lr L (floor (/ n 2)))
        (/(+ (lr L (sub1(/ n 2)))
             (lr L (/ n 2)))
          2))))

Testing:

(median '(1 2 3))
(median '(1 2 3 4))

Output:

2
2 1/2
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Clojure, 65 bytes

#(/(apply +(take 2(drop(-(count %)1)(sort(for[c % i[0 1]]c)))))2)

An other approach I tried:

#(apply +(map *(for[i(range)](get{-2 0.5 -1 1 0 0.5}(-(* i 2)(count %))0))(sort %)))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haxe, 104 bytes

Not amazing, what with the function keywords and a mandatory sorting function …

function f(l,?a)return(l[(a={l[0]+=.0;l.sort(function(x,y)return x>y?1:-1);l.length;})>>1]+l[a-1>>1])/2;

With some whitespace:

function f(l, ?a)
  return (
      l[(a = {
          l[0] += .0;
          l.sort(
               function(x, y) return x > y ? 1 : -1
             );
          l.length;
        }) >> 1]
      + l[a - 1 >> 1]
    ) / 2;

I used l[0]+=.0; to let Haxe know the type of l. The alternative would be l:Array<Float> in the arguments. Then l is sorted, its length is stored in a, and then we basically do (l[a / 2] + l[(a - 1) / 2]) / 2.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ So much abuse of Haxe's "everything is an expression" paradigm going on here, I love it. \$\endgroup\$ – ETHproductions Aug 11 '17 at 18:55
1
\$\begingroup\$

Swift, 93 bytes

let m:([Double])->Double={{c,s in c%2==0 ?(s[c/2-1]+s[c/2])/2:s[c/2]}($0.count,$0.sorted())}

This takes about 10 seconds to compile on my machine but it works. It declares the constant m of type [Double] -> Double.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

T-SQL, 101 67

DECLARE @ table(i real)
INSERT @ values(1),(3),(20),(4)

SELECT top 1PERCENTILE_CONT(.5)WITHIN GROUP(ORDER BY i)OVER()FROM @

Try it out

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C#, 75 bytes

a=>{Array.Sort(a);int m=a.Length;return m%2>0?a[m/2]:(a[m/2-1]+a[m/2])/2;};

An anonymous function which computes the median.

Full program with ungolfed method and test cases:

using System;

public class Program
{
    public static void Main()
    {
        Func<double[],double> f =
        a =>
        {
            Array.Sort(a);  // built-in sort function for arrays
            int m = a.Length;   // stores the number of elements from the array
            return m % 2 > 0 ? a[m/2] : ( a[m/2-1] + a[m/2] ) / 2;
            // if the array has an odd number of elements, the central number will be returned
            // otherwise, the average of the two central elements
        };

        // test cases:
        Console.WriteLine(f(new double[]{1,2,3,4,5,6,7,8,9}));  // 5
        Console.WriteLine(f(new double[]{1,4,3,2}));    // 2.5
        Console.WriteLine(f(new double[]{1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4}));  // 1.5
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It should be System.Array not just Array \$\endgroup\$ – TheLethalCoder Jan 10 '17 at 13:13
1
\$\begingroup\$

CJAM - 21

q~]$__,2/=\_,(2/=+2d/
  • q~] reads input to array
  • $__ sorts it and makes 2 copies
  • , gets length of array
  • 2/ divides that by 2 rounded down
  • = finds the number at that index
  • /_ puts original array at top of stack and copies it
  • ,( gets length of array - 1
  • 2/ divides that by 2 rounded down
  • = finds the number at that index
  • + adds the two array elements extracted 2d/ divides them by 2 as a double (so no rounding)

If the number of array elements N is odd, floor(N/2) = floor((N-1)/2). If N is even the two center elements are selected and the mean is found.

Longer but working alternative strategies:

q~]$__,2/)<_,@W%<&_:+\,d/
q~]$:A,2/_(A,2%$A=@A=+2d/\;
q~]$_Vf*_,2/.5t_W%.+.*:+
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ruby 50 48 Bytes

-2 bytes thanks to @Conor O'Brien

->(l){l.sort!;e=l.length;(l[~-e/2]+l[e/2])/2.0}
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You could save two bytes by removing the parentheses around the first l, and say ~-e instead of (e-1). \$\endgroup\$ – Conor O'Brien Jan 10 '17 at 22:01
1
\$\begingroup\$

Racket, 95 bytes

Using the trusty old match syntax. The pattern (list _ m ... _) matches the middle of a list (that is, it omits the first and last element).

(λ(l)(let f([l(sort l <)])(match l[(list x)x][(list x y)(/(+ x y)2)][(list _ m ... _)(f m)])))

Ungolfed

(λ (l)
  (let f ([l (sort l <)])
    (match l
      [(list x) x]
      [(list x y) (/ (+ x y) 2)]
      [(list _ m ... _) (f m)])))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

8th, 108 105 93 bytes

: m ' n:cmp a:sort a:len 2 n:/mod swap not if n:1- 2 a:slice a:open n:+ 2 n:/ else a:@ then ;

SED (Stack Effect Diagram) is a -- a n

Test

[1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4] m .

Output

1.50000

Ungolfed version (with comments)

\ Median
: m \ a -- a n
    ' n:cmp a:sort \ Sort array
    a:len          \ Get array length
    2 n:/mod       \ Remainder and quotient
    swap           \ Remainder on TOS
    not if         
        \ Array contains an even number of items
        \ Get arithmetic mean of the two values closest to the center of the sorted list
        n:1- 2 a:slice a:open n:+ 2 n:/
    else
        \ Array contains an odd number of items
        \ Get the central value           
        a:@        
    then ;
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 58 + 2 (-ap) = 60 bytes

$_=(@F=sort{$a<=>$b}@F)%2?@F[@F/2]:@F[@F/2]/2+@F[@F/2-1]/2

Try it online!

Input is split into the @F array by the '-a' flag. @F gets sorted. Then, its length is checked to see if it is odd or even. If odd, result is the middle element. If even, result is half of the element to the left of middle plus half of the element to the right of the middle.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Julia 0.6.0 (9 bytes) (6 bytes)

median(a)

median

where a is an array. It's not a very exciting answer but it's cool that Julia has a built in function for the median.

edit: I didn't know I could just write median!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can use median and count it as 6 bytes! \$\endgroup\$ – flawr Aug 11 '17 at 18:34
  • \$\begingroup\$ I didn't know thanks a lot! \$\endgroup\$ – Goysa Aug 11 '17 at 18:42
1
\$\begingroup\$

APL, 26 bytes

{3>≢⍵:(+/÷≢)⍵⋄∇1↓¯1↓⍵[⍋⍵]}

Try it online!

How?

  • 3>≢⍵:(+/÷≢)⍵ - if the length of the array is less then 3, return the average
  • - otherwise
  • ∇1↓¯1↓⍵[⍋⍵] - return the sorted array with the first and last elements removed.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How is this the first APL answer? \$\endgroup\$ – Zacharý Aug 11 '17 at 20:14
1
\$\begingroup\$

GolfScript, 44 bytes

~$.,:l;~l 2%{l 2/$}{{l 2/$}2*+'/2'+}if{\;}l*

Try it online!

Explanation

~$.,:l;~l 2%{l.2/-}{{l 2/$}2*+'/2'+}if{\;}l*   |
~                                              Create array from input string
 $                                             Sort array
  .                                            Duplicate array
   ,                                           Pop and count the top array
    :l                                         Assign variable l
      ;                                        Pop
       ~                                       Convert array into individual integers
        l                                      Push variable l onto stack
          2%                                   Push 2 and perform mod
            {l 2/$}                            If block
            {l 2/                              push variable l and divide by 2
                 $}                            Copy/push value at index (push(stack[pop()]))
                   {{l 2/$}2*+'/2'+}           Else block
                    {l 2/                      Push l/2
                         $}                    Copy
                           2*                  Perform block {} twice
                             +                 Add top two of stack (result of copies)
                              '/2'+}if         Push and add '/2'. End if
                                      {\;}     New block. Swap top two elements then pop
                                          l*   Perform previous block l times
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

dc, 120 122 bytes

9kzsa0si[li:sli1+dsila>A]dsAx[1scddd;sr1-;sli:sr1-:s]sR[lidd1-;sr;s<R1+dsila>S]sS[1si0sclSxlc1=M]dsMxla2/dd1%-;sr.5-;s+2/p

Try it online!

My original code worked for all the provided test cases, but was actually faulty, so +2 bytes for the fix. Dang!

Lots of bytes since dc doesn't have any inbuilt sorting mechanism, and very little in the way of stack manipulation.

9k sets the precision to 9 places since we need the possibility of digits past the decimal point. dc doesn't float, so hopefully this is satisfactory.

zsa0si[li:sli1+dsila>A]dsAx dumps the entirety of the stack into array s, and preserves the number of items in register a.

Macros M, S, and R all make up a bubble sort. M is our 'main' macro, so to speak, so I'll cover that one first.

[1si0sclSxlc1=M]dsMx We reset increment register i to 1, and check register c to 0. We run macro S, which is one pass through the array. If S (actually, R, but S by proxy) made any changes, it would have set register c to one, so if this is the case we loop through M again.

[lidd1-;sr;s<R1+dsila>S]sS One pass through the array. We load the increment counter i, duplicate it twice, and decrement the top version of it by one. Essentially i is always high, so we compare i and i-1. Load the two values from array s, compare them, and if they're going the wrong way we run our swapping macro, R. Then we keep on incrementing i, comparing it to a, and running S until that comparison tells us we've hit the end of our array.

[1scddd;sr1-;sli:sr1-:s]sR An individual instance of swappery in array a. First we set our check register c to 1 so that M knows we made changes to the array. i should still be on the stack from earlier, so we duplicate it three times. We retrieve i indexed item from a, swap our top-of-stack so that i is present again, subtract one from it, and then retrieve that item from a. Here we run into a stack manipulation limitation, so we have to load i again and we store our previous i-1 value into that index in a. Now we just have our old i-indexed a value on the stack and i itself, so we swap these, subtract 1 from i, and replace the value in a.

Eventually M will stop running when it sees no changes have been made, and now that things are sorted we can do the actual median operation.

la2/dd1%-;sr.5-;s+2/p Since a already has the length of array s, we load it and divide by two. Testing for evenness would be costly, so we rely on the fact that dc uses the floor of a non-whole value for its index. We divide a by two and duplicate the value. We then get from s the values indexed by (a/2-.5) and (a/2-((a/2)mod 1)). This gives us the middle value twice for an odd number of values, or the middle two values for an even number. +2/p averages them and prints the result.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

k, 23 bytes

Basically a slightly golfed version of q's canonical med in k.

{avg x(<x)@_.5*-1 0+#x}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Jelly, 2 bytes

Æṁ

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

PHP, 70 77 bytes

Not exactly optimal but works.

Requires that the values are passed over GET.

<?sort($_GET);die(($C=count($G=$_GET))&1?$G[~-$C/2]:($G[$C/2]+$G[$C/2-1])/2);

The result will be displayed in the browser and as the return code.


Thanks to Titus for fixing it, at the cost of 7 bytes.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1) You have a typo: ~~ should be ~-. 2) You compute the arithmetic mean of the whole array, but should only "of the two values closest to the center"; i.e. ?$G[~-$C/2]:($G[$C/2]+$G[$C/2-1])/2. \$\endgroup\$ – Titus Sep 30 '18 at 5:20
  • \$\begingroup\$ Thank you for the fix. It is sad that it got longer :/ \$\endgroup\$ – Ismael Miguel Sep 30 '18 at 12:09
1
\$\begingroup\$

Haskell 1.2 (Gofer), 44 bytes

f[x]=x
f[x,y]=(x+y)/2.0
f(x:y)=f.init$sort y

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 2 bytes

Åm

Try it online or verify all test cases.

No need for an explanation, since Åm is a builtin which will:

Median. Sorts the list, then returns either the middle element or the average of the middle elements depending on the parity of the length of the list.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Lua, 64 63 bytes

function f(t)table.sort(t)h=#t//2return(t[h+1]+t[h+#t%2])/2 end

Try it online!

Sort table, get the position halfway through the table by integer-dividing table length by two, return average of element at half position plus one and element at half position if table length is even, else at half position plus one.

This solution is only valid in Lua 5.3 and onwards where there is integer division, // (and where integers can be squished right next to the keyword return). In Lua 5.1, the equivalent is math.floor(a/b), which would add several bytes.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can remove the space between 2 and return \$\endgroup\$ – Jo King Dec 22 '18 at 11:12
  • \$\begingroup\$ Thanks! I didn't try that, though I noticed before that integer plus keyword (with no intervening space) sometimes works in Lua 5.3; for instance if 0then end is valid. \$\endgroup\$ – cyclaminist Dec 22 '18 at 11:17
  • \$\begingroup\$ I think the rule is that the keyword can't start with a letter that might make the number look like a hexadecimal. For example, you can't remove spaces before end, do, else etc. \$\endgroup\$ – Jo King Dec 22 '18 at 11:18
  • \$\begingroup\$ Oh yeah, the lexer segments 0end as 0e, nd because it starts by simply reading a series of hexadecimal digits, decimal dots, or exponent markers into the buffer. So that part of the process accepts things like 1e+10e-10 or 1.1.1 before trying to get their numerical value and throwing a "malformed number" error. \$\endgroup\$ – cyclaminist Dec 22 '18 at 11:30
1
\$\begingroup\$

Tcl, 100 bytes

proc M L {expr ([lindex [set S [lsort -r $L]] [set h [expr [llength $L]/2]]]+[lindex $S end-$h])/2.}

Try it online!


Tcl, 97 bytes

proc M L {expr ([lindex [set S [lsort $L]] [set h [expr [llength $L]/2]]]+[lindex $S end-$h])/2.}

Try it online!

Tcl, 123 bytes

proc M L {set I [lindex [set S [lsort $L]] [expr [set n [llength $L]]/2]]
expr {$n%2?$I:($I+[lindex $S [expr $n/2-1]])/2.}}

Try it online!

Tcl, 124 bytes

proc M L {set n [llength [set S [lsort $L]]]
set I [lindex $S [expr $n/2]]
expr {$n%2?$I:($I+[lindex $S [expr $n/2-1]])/2.}}

Try it online!

Tcl, 133 bytes

proc M L {proc G L\ i {lindex $L [expr $i]}
expr {[set n [llength [set S [lsort $L]]]]%2?[G $S $n/2]:([G $S $n/2]+[G $S $n/2-1])/2.}}

Try it online!

Tcl, 135 bytes

proc M L {expr {[set n [llength [set S [lsort $L]]]]%2?[lindex $S [expr $n/2]]:([lindex $S [expr $n/2]]+[lindex $S [expr $n/2-1]])/2.}}

Try it online!

Still very ungolfed, my first minimum viable product!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Save some bytes with recursive version (translate from my python3 version) -6 bytes \$\endgroup\$ – david Dec 22 '18 at 15:34
  • \$\begingroup\$ @david Meanwhile you posted, I was outgolfing myself. I tried to golf your suggestion a little more as tio.run/##jU/LCoMwELz7FXPw0FJqffYB/… , but I've already shortened my code more than it. Thanks anyway \$\endgroup\$ – sergiol Dec 22 '18 at 16:05
  • \$\begingroup\$ OK right! Your code is great, I propose you to save still some : 118 bytes \$\endgroup\$ – david Dec 22 '18 at 16:18
  • \$\begingroup\$ and even more (-2) in removing an unuseful pair of final braces! \$\endgroup\$ – david Dec 22 '18 at 16:20
  • \$\begingroup\$ Could not grasp how do you distinguish the odd from the even case. Are you doing the average with self in the last line for the odd case? \$\endgroup\$ – sergiol Dec 22 '18 at 16:47
0
\$\begingroup\$

APL(NARS), 31 chars, 62 bytes

{2÷⍨x[⌊k]+(⌈k←2÷⍨1+≢⍵)⌷x←⍵[⍋⍵]}

test

  t←{2÷⍨x[⌊k]+(⌈k←2÷⍨1+≢⍵)⌷x←⍵[⍋⍵]}
  t 5 4 3 2 1     
3
  t 4 3 2 1     
2.5
  t 5 40 30 2 1     
5
  t 5 40 30 2     
17.5
  35÷2
17.5
   t ,80
80
  t 9 3 4 8 7 6
6.5
| improve this answer | |
\$\endgroup\$
1
2

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.