On Fri, 05 Oct 2007 16:49:31 -0500, "Mumia W."
<paduille.4061.mumia.w+nospam@earthlink.net> wrote:

>I know the mean can be calculated "on the fly"--without storing all of 
>the values to be examined, but I can't see how this is to be done with 
>the median; I don't think it's possible.

Sure it is possible:

##</code><code>##

#!/usr/bin/perl

use strict;
use warnings;
use List::Util 'sum';
use constant TESTS => 20;
use Test::More tests => TESTS;

sub naive {
    my @arr = map +($_) x $_[$_], 0..$#_;
    @arr % 2 ? 
      @arr[(@arr-1)/2] :
      (@arr[@arr/2 - 1] + @arr[@arr/2])/2;
}

sub findidx {
    my $i=shift;
    ($i -= $_[$_])<0 and return $_ for 0..$#_;
}

sub smart {
    my $t=sum @_;
    $t%2 ?
      findidx +($t-1)/2, @_ :
      (findidx($t/2-1, @_) + findidx($t/2, @_))/2;
}

for (1..TESTS) {
    my @a=map int rand 10, 0..5;
    is smart(@a), naive(@a), "Test @a";
}

__END__

##</code><code>##

sub smart {
    my $t=sum @_;
    if ($t%2) {
        my $i=($t-1)/2;
        ($i -= $_[$_])<0 and return $_ for 0..$#_;
    } else {
        my $i=$t/2-1;
        my ($found1, $found2);
        for (0..$#_) {
            ($found1=$_), last if ($i -= $_[$_])<0;
        }
        my $j=$t/2;
        for (0..$#_) {
            ($found2=$_), last if ($j -= $_[$_])<0;
        }
        return ($found1+$found2)/2;
    }
}

##</code><code>##

sub smart {
    my $t=sum @_;
    if ($t%2) {
        my $i=($t-1)/2;
        ($i -= $_[$_])<0 and return $_ for 0..$#_;
    } else {
        my $acc=0;
        for my $i ($t/2-1, $t/2) {
            for (0..$#_) {
                ($acc += $_), last if ($i -= $_[$_])<0;
            }
        }
        return $acc/2;
    }
}