#!/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;
}

# ($index_low, $index_high) =
#   binary_range_string( \@array, $target_low, $target_high );
#      @array is sorted strings
#      On return:
#         $array[$index_low..$index_high] are all of the
#           values between $target_low and $target_high inclusive
#           (if there are no such values, then $index_low will
#           equal $index_high+1, and $index_low will indicate
#           the position in @array where such a value should
#           be inserted, i.e., any value in the range should be
#           inserted just before element $index_low

sub binary_range_string {
    my ($array, $target_low, $target_high) = @_;
    my $index_low  = binary_string( $array, $target_low );
    my $index_high = binary_string( $array, $target_high );

    --$index_high
        if $index_high == @$array ||
                            $array->[$index_high] gt $target_high;

    return ($index_low,$index_high);
}

@year = qw(0101 0115 0131 0201 0215 0228 0301 0315 0331);

($Feb_start, $Feb_end) = binary_range_string(\@year, '0201', '0229');

# Prints 3, 5

print "$Feb_start, $Feb_end\n";