History of Idiom 124 > diff from v29 to v30
Edit summary for version 30 by daxim:
New Perl implementation by user [daxim]
New Perl implementation by user [daxim]
↷
Version 29
2019-09-26, 19:49:45
Version 30
2019-09-27, 09:34:00
Idiom #124 Binary search for a value in sorted array
Write function binarySearch which returns the index of an element having value x in sorted array a, or -1 if no such element.
Idiom #124 Binary search for a value in sorted array
Write function binarySearch which returns the index of an element having value x in sorted array a, or -1 if no such element.
Extra Keywords
dichotomic dichotomyExtra Keywords
dichotomic dichotomyCode
sub binary_search {
my ($x, $A, $lo, $hi) = @_;
$lo //= 0;
$hi //= @$A;
my $mid = int(($lo + $hi) / 2);
for ($x cmp $A->[$mid]) {
use experimental 'switch';
return $mid when 0;
return -1 if 1 == $hi - $lo;
return binary_search($x, $A, $lo, $mid) when -1;
return binary_search($x, $A, $mid, $hi) when 1;
}
}