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]