Here's an O(1) solution for small (<256) numbers:

#! perl -slw
use strict;
use List::Util qw[ reduce ]; $a = $b;

my @array = (1,4,5,6,7,9,10,23,34,44,55,56,57,59,70,80,90,100);
my $yardstick = '';
reduce {
    my $n = $a;
    $yardstick .= chr( $a ), $n++ while $n < $b;
    $b;
} @array;

print "$_ : ", ord( substr $yardstick, $_-1, 1 ) for map 10 * $_- 5, 1
+ .. 10;

__END__
c:\test>junk8
5 : 5
15 : 10
25 : 23
35 : 34
45 : 44
55 : 55
65 : 59
75 : 70
85 : 80
95 : 90
[download]

This can fairly easily be adapted to handle numbers upto 64k if you have 128k of ram to spare. Larger number ranges obviously require more ram. Negative numbers can also be handled with minor adaptions.