I recommend using grep in this case. One thing to observe on everything proposed so far: the use of s/// within sub search has side effects outside of the the sub as it modifies the input! If it is an anonymous array reference it does not make any difference, but otherwise it might create problems later. See the difference between the line commented out below and the following one.

use strict;
use warnings;

sub search {
        my ( $data, $neg, $pos ) = @_;
        my $regp = join "|", @$pos;
#        my $regn = join "|", map { s/^-//, $_ } @$neg; # warning:  si
+de effects outside of sub search!
        my $regn = join "|", map { /^-?(.*)/ } @$neg; # no side effect
+s
        my @results = grep { /$regp/ && !/$regn/ } @$data;
        return \@results;
}

my $neg = ["-bo"];
my $results = search(["bobcat", "boomerang", "beer", "bat", "aaa" ], $
+neg, ["b"]);
print "@$results\n";
print "@$neg\n";
[download]