#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(cmpthese);

my $limit = shift @ARGV || 1e4;
my @a = sort {$a <=> $b } map { rand(2**20) } 0..($limit+1);
print "Done generating list\n";

my $search_for = $a[int($limit / 3)];

sub brutal {
    for (0 .. $limit){
        return $_ if $a[$_] > $search_for;
    }
}

sub binary {
    my ($left, $right) = (0, $limit);
    while ($right - $left > 10){
        my $tmp = ($right+$left) / 2;
        if ($a[$tmp] > $search_for){
            $right = $tmp;
        } else {
            $left = $tmp;
        }
    }
    for ($left .. $right){
        return $_ if $a[$_] > $search_for;
    }
}
my $brutal = brutal();
my $binary = binary();
print $brutal, ' ', $binary, "\n";

cmpthese(-2, {
        binary  => \&binary,
        brutal  => \&brutal,
    });