时间戳

首页 > 解决方案 > Raku 中的简洁（一行？）二分搜索

algorithm - Raku 中的简洁（一行？）二分搜索

问题描述

标签： algorithmbinary-searchrakurakudo

解决方案

这是一种在技术上满足我的要求的方法（因为它适合在单个正常长度线上的函数体）。[但请参阅下面的编辑以获取改进的版本。]

sub binary-search(@a, \i is copy = my $=0, :target($t)) {
  for +@a/2, */2 … *≤1 {@a[i] cmp $t ?? |() !! return @a[i] with i -= $_ × (@a[i] cmp $t)} 
}

# example usage (now slightly different, because it returns the index)
my @a = ((^20 .pick(*)) Z=> 'a'..*).sort;
say @a[binary-search(@a».key, :target(17))];
say @a[binary-search(@a».key, :target(1))];

我仍然对这段代码不太满意，因为它失去了一点可读性——我仍然觉得可能/应该有一种简洁的方法来进行二进制排序，同时也清楚地表达了底层逻辑。使用 3 路比较感觉就像是在那个轨道上，但仍然不完全在那里。

[编辑：经过深思熟虑，我想出了一个更易读的上述版本，使用reduce.

sub binary-search(@a, :target(:$t)) {
  (@a/2, */2 … *≤.5).reduce({ $^i - $^pt×(@a[$^i] cmp $t || return @a[$^i]) }) && Nil
}

在英语中，它读作：对于从数组中点开始并下降 1/2 的序列，将索引移动$^i序列中下一个项目的值 - 移动方向取决于项目是否位于该指数大于或小于目标。继续直到找到目标（在这种情况下，返回它）或完成序列（这意味着目标不存在；返回Nil）]

推荐阅读