Concise (one line?) binary search in Raku

Question

Many common operations aren't built in to Raku because they can be concisely expressed with a combination of (meta) operators and/or functions. It feels like binary search of a sorted array ought to be expressable in that way (maybe with .rotor? or …?) but I haven't found a particularly good way to do so.

For example, the best I've come up with for searching a sorted array of Pairs is:

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)
}

That's not awful, but I can't shake the feeling that it could be an awfully lot better (both in terms of concision and readability). Can anyone see what elegant combo of operations I might be missing?

user_10173009 · Answer

Here's one approach that technically meets my requirements (in that the function body it fits on a single normal-length line). [But see the edit below for an improved version.]

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

I'm still not super happy with this code, because it loses a bit of readability – I still feel like there could/should be a concise way to do a binary sort that also clearly expresses the underlying logic. Using a 3-way comparison feels like it's on that track, but still isn't quite there.

[edit: After a bit more thought, I came up with an more readable version of the above using reduce.

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

In English, that reads as: for a sequence starting at the midpoint of the array and dropping by 1/2, move your index $^i by the value of the next item in the sequence – with the direction of the move determined by whether the item at that index is greater or lesser than the target. Continue until you find the target (in which case, return it) or you finish the sequence (which means the target wasn't present; return Nil)]

Concise (one line?) binary search in Raku

1 Answers