quest8.pl

#!/usr/bin/env perl 
#===============================================================================

use Modern::Perl '2015';
use utf8;

use Benchmark qw(:all);

my @array = sort { $a <=> $b } ( 1 .. 10_000 );
my @numbers = ( -1, 0, 1, 5, 500, 5000, 10_000, 11_000 );

timethese(10_000, {
    binsearch_good => sub {
            foreach my $number ( @numbers ) {
                my $result = binsearch_good( $number, \@array );
            }
        },
    binsearch_bad => sub {
            foreach my $number ( @numbers ) {
                my $result = binsearch_bad( $number, \@array );
            }
        },
});

cmpthese(10_000, {
    binsearch_good => sub {
            foreach my $number ( @numbers ) {
                my $result = binsearch_good( $number, \@array );
            }
        },
    binsearch_bad => sub {
            foreach my $number ( @numbers ) {
                my $result = binsearch_bad( $number, \@array );
            }
        },
});

sub binsearch_bad {
    my ( $number, $array ) = @_;

    my $last = scalar @$array;

    my $first = 0;
    while ( $first < $last ) {
        my $mid = int( $first + ( $last - $first ) / 2 );
        if ( $number <= $array->[$mid] ) {
            $last = $mid;
        }
        else {
            $first = $mid + 1;
        }
    }

    return $last;
}

sub binsearch_good {
    my ( $number, $array ) = @_;

    my $last = scalar @$array;

    if ( $last == 0 ) {
        return undef;
    }
    elsif ( $array->[0] > $number ) {
        return 0;
    }
    elsif ( $array->[$#$array] < $number ) {
        return $#$array;
    }

    my $first = 0;
    while ( $first < $last ) {
        my $mid = int( $first + ( $last - $first ) / 2 );
        if ( $number <= $array->[$mid] ) {
            $last = $mid;
        }
        else {
            $first = $mid + 1;
        }
    }

    return $last;
}