I don't think you can avoid a loop of some sort - either way you have to work out the index of the element in the sorted keys.

Here's my quick stab:

#!/usr/bin/perl
use strict;
use warnings;

my %hash = ('1'  => 'cat',
            '3'  => 'mouse',
            '5'  => 'whale',
            '12' => 'dog',
            );

my $top_hash_key = (sort {$a<=>$b} keys %hash)[-1];

my $next_val = retrieve(2);
print "retrieve 2: $next_val\n";

my $other_val = retrieve(8);
print "retrieve 8: $other_val\n";

my $too_high = retrieve(15);
print "retrieve 15: $too_high\n";

sub retrieve {
    my $i = $_[0];
    1 while (!defined $hash{$i} and $i++<$top_hash_key);
    return defined $hash{$i} ? $hash{$i} : '';
}
[download]

.02

cLive;-)