# &binsearch($key, $arrayref)
#
# Searches the array referenced by $arrayref for
# the string $key using binary search.  The array
# must be sorted.
sub binsearch
{
    my $key      = shift;
    my $arrayref = shift;

    # $lower contains the index of the lowest element
    # of the range of the array we're searching.  $upper
    # is the index of the highest element.
    my $lower    = 0;
    my $upper    = $#$arrayref;

    my ($index, $result);

    # Loop until the upper and lower indexes meet in the middle
    while ($upper >= $lower)
    {
        # Divide the range of the array we're searching in half.
        # Round fractions to the nearest integer.
        $index  = int($lower + (($upper - $lower) / 2) + .5);

        # Compare the element in the middle of the range to the
        # key we're searching for.
        $result = $key cmp $$arrayref[$index];

        if ($result < 0)
        {
                # If our search key is lower than the element
                # in the middle of the range, set the index of
                # the upper bound on the range to 1 less than
                # that of the middle element and loop again
                $upper = $index - 1;
        } elsif ($result == 0) {
                # If our search key is equal to the middle
                # element, we found what we're looking for.
                return 1;
        } elsif ($result > 0) {
                # If our search key is higher than the middle
                # element of the range, raise the lower end of
                # the range to 1 more than the middle's index.
                $lower = $index + 1;
        }
    }
}