Use hash. If you have existing array, convert that into a hash and convert back to array for any purpose served better with array. (Order may be altered in following case, if that's ok.)

@array = (1,2,3,4);
%hash = map { $_, 1} @array;
@new_elements = (1,3,5,7,9);
$hash{$_} = 1 for @new_elements;
@array = keys %hash;
[download]