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