Perl二维Hash如何快速查询多个价格区间对应的主键，避免重复遍历

高效实现方案 #

核心思路是仅遍历1次原哈希构建排序索引，后续所有区间查询都通过二分查找完成，整体时间复杂度从原有O(N*K)（N为10万条数据，K为上百个查询区间）降至O(N + K*logN)，性能提升上百倍。

步骤1：单次遍历原哈希，构建排序索引 #

仅执行1次全量遍历，生成按价格升序排列的索引结构，后续不需要再访问原哈希：

# 遍历一次原哈希，提取价格与对应水果名
my @price_index;
while (my ($fruit_name, $props) = each %fruits) {
    push @price_index, { price => $props->{price}, name => $fruit_name };
}
# 按价格升序排序索引
@price_index = sort { $a->{price} <=> $b->{price} } @price_index;
# 提取单独的价格数组，方便后续二分查找
my @sorted_prices = map { $_->{price} } @price_index;

步骤2：二分查找定位区间，批量提取匹配结果 #

任意区间查询都不需要遍历全量数据，直接通过二分查找定位区间的左右边界即可：

# 可直接用Perl成熟的二分查找模块，不需要自己手写实现
use List::BinarySearch qw( binsearch_left binsearch_right );

# 示例查询价格区间35~55
my ($min_price, $max_price) = (35, 55);
# 左边界：第一个大于等于区间最小值的下标
my $left_idx = binsearch_left { $a <=> $b } $min_price, @sorted_prices;
# 右边界：最后一个小于等于区间最大值的下标
my $right_idx = binsearch_right { $a <=> $b } $max_price, @sorted_prices;

# 提取匹配的水果名
my @result;
if (defined $left_idx && defined $right_idx && $left_idx <= $right_idx) {
    @result = map { $_->{name} } @price_index[$left_idx .. $right_idx];
}
# 此时@result即为['Orange','Grape']，符合预期

可选优化（适用价格重复率高的场景） #

如果大量水果价格相同，可以提前按价格分组，进一步降低查询时的遍历量：

# 按价格分组构建索引
my %price_group;
while (my ($fruit_name, $props) = each %fruits) {
    push @{$price_group{$props->{price}}}, $fruit_name;
}
# 排序所有唯一价格
my @sorted_unique_prices = sort { $a <=> $b } keys %price_group;

# 查询逻辑和上面一致，匹配到价格区间后直接取分组的水果列表即可
my $left_p = binsearch_left { $a <=> $b } $min_price, @sorted_unique_prices;
my $right_p = binsearch_right { $a <=> $b } $max_price, @sorted_unique_prices;
my @result;
if (defined $left_p && defined $right_p && $left_p <= $right_p) {
    @result = map { @{$price_group{$_}} } @sorted_unique_prices[$left_p .. $right_p];
}

如果不想引入第三方依赖，手写左右边界的二分查找逻辑也非常简单，成熟实现仅几十行代码，不需要额外安装模块。

内容的提问来源于stack exchange，提问作者learning_math