#!/usr/bin/perl

# Also see the binary_search() subroutine in Chapter 1.
# $index = binary_string( \@array, $target )
#        @array is sorted strings
#    on return,
#        either (if the element was in the array):
#           # $index is the element
#           $array[$index] eq $target
#        or (if the element was not in the array):
#           # $index is the position where the element should be inserted
#           $index == @array or $array[$index] gt $target
#           splice( @array, $index, 0, $target ) would insert it
#               into the right place in either case
#
sub binary_string {
     my ($array, $target) = @_;

     # $low is first element that is not too low;
     # $high is the first that is too high
     #
     my ( $low, $high ) = ( 0, scalar(@$array) );

     # Keep trying as long as there are elements that might work.
     #
     while ( $low < $high ) {
         # Try the middle element.

         use integer;
         my $cur = ($low+$high)/2;
         if ($array->[$cur] lt $target) {
	     $low  = $cur + 1;                     # too small, try higher
	 } else {
	     $high = $cur;                         # not too small, try lower
	 } 
     }
     return $low;
}

my $word = "mass";

@keywords = qw(About a third of the bias observed in his own dice could be explained
	       by the effect of asymmetric mass on the final fall.);

print "Index of $word in \@keywords is: ", binary_string( \@keywords, $word ), "\n";