Unless your array of numbers is huge, I'd use a simple linear search:

sub first { 
    my $aref = shift; 
    $aref->[ $_ ]+1 != $aref->[ $_+1 ] 
        and return $aref->[ $_ ]+1 
        for 0 .. $#$aref-1; 
};;

@a = 1000..1100;;
splice @a, rand(100), 1 for 1 .. 10;;

print @a;;
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 
+1014 1015 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028
+ ...

print first( \@a );;
1016
[download]

Exactly? The array contains 1001, 1002, 1003? Or the array has indexes 1001, 1002, 1003?

For example:

use strict;
use warnings;
use List::MoreUtils qw/firstidx/;

@array = qw/ fred tom jenny jeff claire /;
$array[3] = undef;
my $available_index = firstidx { not defined $_ } @array; 
$array[$available_index] = 'peter';
print "@array\n";
__END__
fred tom jenny peter claire
[download]