Code Golf: Shortest code to find a weighted median?

Question

My try at code golfing.

The problem of finding the minimum value of ∑W_i*|X-X_i| reduces to finding the weighted median of a list of x[i] with weights w[i] (see below for definition). How will you do that with a shortest, simplest and most beautiful program?

Here's how my code looked originally (explanation is in the answer to the question and short version is posted as one of the answers below).

    #define zero(x) ( abs(x) < 1e-10 )  /* because == doesn't work for floats */

    float sum = 0;
    int i;

    for (i = 0; i < n; i++) 
         sum += w[i];
    while (sum > 0) 
         sum -= 2*w[--i];

    right = x[i]             // the rightmost minimum point
    left  = ( zero(sum) && zero(w[i]-w[i-1]) ) ? x[i-1] : right;
    answer = (left + right) / 2;

(Actually, it's been already heavily optimized as you see variables i and sum reused)

Rules

Floats and integers: different languages have different floating point arithmetic standards, so I reformulate the problem to have x[i] and w[i] to be integers and you can return twice the value of the answer (which is always integer) if you prefer. You can return, print or assign the answer to variable.

Definition of weighted median and clarifications:

• Median of sorted array x[i] of length n is either x[n/2] or (x[n/2-1/2]+x[n/2+1/2])/2 depending on whether n is odd or even
• Median of unsorted array is the median of array after sort (true, but our array is sorted)
• Weighted median of x[i] with integer positive weights w[i] is defined as the median of larger array where each occurrence of x[i] has been changed into w[i] occurrences of x[i].

What I hope to see

One of the reasons for asking is that I assume the most suitable language will have trivial array summation and iteration with lambdas. I thought a functional language could be reasonable, but I'm not sure about that - so it's part of the question. My hope is to see something like

    // standard function   add  :=  (a,b) :-> a + b 
    myreduce := w.reduce  
        with:  add  
        until: (value) :-> 2*value >= (w.reduce with:add)
    answer = x [myreduce  from:Begin] + x [myreduce  from:End]

Dunno if there's any language where this is possible and is actually shorter.

Test data

static int n = 10;
for (int j = 0; j < n; j++) {
        w[j] = j + 1;
        x[j] = j;
}

Answer: 6 or 12.

static int n = 9;
int w[n], x[n] ;
for (int j = 0; j < n; j++) {
    w[j] = j + ((j<6) ? 1 : 0);
    x[j] = j + 1;
}

Answer: 6.5 or 13.

Answer 1

J

Go ahead and type this directly into the interpreter. The prompt is three spaces, so the indented lines are user input.

   m=:-:@+/@(((2*+/\)I.+/)"1@(,:(\:i.@#))@[{"0 1(,:(\:i.@#))@])

The test data I used in my other answer:

   1 1 1 1 m 1 2 3 4
2.5
   1 1 2 1 m 1 2 3 4
3
   1 2 2 5 m 1 2 3 4
3.5
   1 2 2 6 m 1 2 3 4
4

The test data added to the question:

   (>:,:[)i.10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8  9
   (>:m[)i.10
6
   (([+<&6),:>:)i.9
1 2 3 4 5 6 6 7 8
1 2 3 4 5 6 7 8 9
   (([+<&6)m>:)i.9
6.5

---

   i =: (2 * +/\) I. +/

First index such that total sum is greater than or equal to double the accumulated sum.

   j =: ,: (\: i.@#)

List and its reverse.

   k =: i"1 @ j @ [

First indices such that -see above- of the left argument and its reverse.

   l =: k {"(0 1) j @ ]

Those indices extracted from the right argument and its reverse, respectively.

   m =: -: @ +/ @ l

Half the sum of the resulting list.