Alternatively, you can make use of the fact the list is sorted (again, untested): 

my @uids = ....;  # List of sorted uids
my $uid = 1001;
for (my $i = 0; $i < @uids; $i++) {
    next if $uids[$i] < $uid;
    last unless $uids[$i] == $uid;
    $uid++;
}
say "First unused uid: $uid";