=begin pod
=head1 Binary search algorithm
In computer science, B«binary search» is a search algorithm that finds the
position of a target value within a sorted array. More info in its
L.
=head1 Algorithm
The pseudocode for the iterative procedure is as follows:
=begin code :allow('B')
B binary_search(A, n, T):
L := 0
R := n − 1
B L <= R:
m := floor((L + R) / 2)
B A[m] < T:
L := m + 1
B A[m] > T:
R := m - 1
B:
B m
return unsuccessful
=end code
=head2 Raku implementation
=begin code :allow('B')
B_{ binary-search( @arr, Int $up-to where * ≤ @arr.end, $target ) {
my Int:D ($low, $high) = 0, $up-to;
B $low ≤ $high {
my Int:D $m = (($low + $high)/2).floor;
B @arr[$m] < $target { $low = $m + 1 }
B @arr[$m] > $target { $high = $m - 1 }
B { return $m }
}
B False;
}
=end code
=end pod
}