#!/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__