# Warning: Untested code, almost definitely has off by one errors!

# Given a frequency table in @freq, build a summed frequency table.
my $sum;
@sf = map {$sum += $_} @freq;

# Now we choose a random number in the range of total frequency sum
my $target = rand($sum);

# To find out what the Answer is (weighted freq from 0 to n),
# we now find n such that $sf[n-1]< $target < $sf[n]

# We keep track of the numbers we know $n is between
my $a = 0; my $b = @sf; my $n;

# repeat until we narrow down to one answer
while ($a < $b) {
    $n = int(($a + $b) / 2);
    if ($sf[$n] < $target) {
        $a = $n;
    } elsif ($sf[$n-1] > $target) {
        $b = $n;
    } else { 
        # $target < $sf[n] and $target > $sf[n-1],
        # so we have an answer.
        last;
    }
}

print "I found $n\n";