=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<Wikipedia article|https://en.wikipedia.org/wiki/Binary_search_algorithm>.

=head1 Algorithm

The pseudocode for the iterative procedure is as follows:

=begin code :allow('B')
B<function> binary_search(A, n, T):
    L := 0
    R := n − 1
    B<while> L <= R:
        m := floor((L + R) / 2)
        B<if> A[m] < T:
            L := m + 1
        B<else if> A[m] > T:
            R := m - 1
        B<else>:
            B<return> m
    return unsuccessful
=end code

=head2 Raku implementation

=begin code :allow('B')
B<sub> binary-search( @arr, Int $up-to where * ≤ @arr.end, $target ) {
    my Int:D ($low, $high) = 0, $up-to;

    B<while> $low ≤ $high {
        my Int:D $m = (($low + $high)/2).floor;
        B<if>      @arr[$m] < $target { $low  = $m + 1 }
        B<else if> @arr[$m] > $target { $high = $m - 1 }
        B<else>                       { return $m      } 
    }
    B<return> False;
}
=end code

=end pod