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

Question

许多常见的操作都没有内置到 Raku 中，因为它们可以用（元）运算符和/或函数的组合来简洁地表达。这感觉就像折半查找有序数组的应该是那样的可表达的（也许用.rotor？或者…？），但我还没有找到一个特别好的办法这样做。

例如，我想出的用于搜索已排序的 Pairs 数组的最佳方法是：

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）]