I think others have shown why your code doesn't work (prints 1 instead of 2).

If speed is of interest, I would use the List::Util qw(first) function. Instead of map or grep which will process the entire input list, "first" will "short circuit" and give up processing the input list when it finds a "match". If on average you are searching for something midway in the list, this will be 2x as fast because on average you are only searching 1/2 the list before finding a match instead of searching the entire list every time no matter what.

#!/usr/bin/perl

use strict;
use warnings;
use List::Util qw(first);

my @array=();
$array[0]=  [qw(ape  bear     cat)];
$array[1] = [qw(dog  emu      fox)];
$array[2] = [qw(goat horse    ibex)];
$array[3] = [qw(mule elephant zebra)];


my $result4 = first{$array[$_][0] =~ /goat/}0..$#array;
print $result4."\n";  #prints: 2

# This is logically the same thing, 
# However, the List::Util function written in C
# probably runs much faster

foreach my $i (0..$#array)
{
   if ($array[$i][0] =~ /goat/)
   {
       print "$i\n";
       last;
   }
}
[download]

Update: my $result4 = first{$array$_[0] eq "goat"}0..$#array;
will be much faster than using the regex engine to test for "goat"

Update2: I am curious about your application? If you are using linear search and that is an issue, there probably are better data structures. On the other hand, this morning I had a DB application where I needed to build a histogram of one column. My SQL "kung-fu" isn't so hot, so I just read all 1.3M rows and made a Perl hash table. Takes less than 1 second - so what? In my application this one second doesn't matter a bit. All this stuff is application dependent. There are other operations where I ask SQL to do things that would take a lot of Perl code.