Here's a modified binary search that may help with the problem if there are lots of price changes per part:

use strict;
use warnings;

my %partprice =
  (
  1 =>
    {
    '2005-01-01' => 1.99, # new year special.
    '2005-01-02' => 8.99, # back to normal.
    '2005-02-15' => 9.99, # price bump.
    '2005-04-01' => 9.49, # on sale.
    '2005-04-08' => 10.99, # sale's over.
    },
  );

my %hPrices = %{$partprice{1}};
my @aPrices = map {"$_ $hPrices{$_}"} sort keys %hPrices;
print ((join "\n", @aPrices) . "\n");

my $date = '2005-01-00';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-01-01';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-01-02';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-01-03';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-02-16';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-04-07';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-04-08';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";
$date = '2005-04-09';
print "The price on the $date was " . FetchPrice (1, $date) . "\n";


sub FetchPrice
{
my ($partnbr, $date) = @_;
my %hPrices = %{$partprice{$partnbr}};
my @aPrices = map {[$_, $hPrices{$_}]} sort keys %hPrices;

return $aPrices[0]->[1] if $date le $aPrices[0]->[0];
return $aPrices[-1]->[1] if $date ge $aPrices[-1]->[0];

my $posmin = 0;
my $posmax = $#aPrices;

while (1)
  {
  my $mid = int (($posmin + $posmax + 1) / 2);

  if ($aPrices[$mid]->[0] lt $date)
    {
    return $aPrices[$mid - 1]->[1] if $mid == $posmin;
    $posmin = $mid;
    }
  elsif ($aPrices[$mid]->[0] gt $date)
    {
    return $aPrices[$mid - 1]->[1] if $mid == $posmax;
    $posmax = $mid;
    }
  else
    {
    return $aPrices[$mid]->[1];
    }
  }
}
[download]

2005-01-01 1.99
2005-01-02 8.99
2005-02-15 9.99
2005-04-01 9.49
2005-04-08 10.99
The price on the 2005-01-00 was 1.99
The price on the 2005-01-01 was 1.99
The price on the 2005-01-02 was 8.99
The price on the 2005-01-03 was 8.99
The price on the 2005-02-16 was 9.99
The price on the 2005-04-07 was 9.49
The price on the 2005-04-08 was 10.99
The price on the 2005-04-09 was 10.99
[download]