简洁(一行？)Raku中的二进制搜索

Question

许多常见的操作都没有内置到Raku中，因为它们可以用(meta)操作符和/或函数的组合简洁地表示。这感觉就像对排序数组的二进制搜索应该以这种方式表示(也许用.rotor？还是…?)但我还没有找到一个特别好的方法来做到这一点。

例如，我找到的搜索排序对数组的最佳方法是：

sub binary-search(@a, $target) {
    when +@a ≤ 1 { @a[0].key == $target ?? @a[0] !! Empty }
    &?BLOCK(@a[0..^*/2, */2..*][@a[*/2].key ≤ $target], $target)
}

这并不可怕，但我无法摆脱的感觉是，这可能是一个可怕的更好(在简洁和可读性方面)。有人能看到我可能错过了什么优雅的组合吗？

Answer 1

这里有一种方法在技术上满足了我的要求(因为它的功能主体适合于一条正常长度的行)。但是，请参阅下面的编辑以获得更好的版本。

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))];

我仍然对这段代码不太满意，因为它失去了一点可读性--我仍然觉得应该有一种简洁的方法来做同样清楚地表达底层逻辑的二进制排序。用三面比较感觉就像在那条赛道上，但还不完全是这样。

[编辑：经过更多的思考后，我想出了一个使用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)]