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

Question

许多常用操作并未内置于 Raku 中，因为它们可以使用（元）运算符 and/or 函数的组合来简洁地表达。它感觉像排序数组的二进制搜索应该以这种方式表达（也许用 .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))];

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

[edit：经过深思熟虑，我使用 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 移动序列中下一项的值 – 使用移动的方向取决于该索引处的项目是大于还是小于目标。继续，直到找到目标（在这种情况下，return 它）或完成序列（这意味着目标不存在；return Nil)]

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

Concise (one line?) binary search in Raku

algorithm

binary-search

raku

rakudo