What the heck... Yet Another non-O(n), sort-based solution, this one using a Guttman-Rosler transform (GRT).

c:\@Work\Perl\monks>perl -wMstrict -le
"my @ra = qw(12 -3 4 71 5 -11 -0.99999 -598 -100203 0.99999 4);
 ;;
 my ($i_lnn) =
   map unpack('x[N] N', $_),
   sort
   map { $ra[$_] >= 0 && $ra[$_] == int($ra[$_]) ? pack('N N', $ra[$_]
+, $_) : () }
   0 .. $#ra
   ;
 ;;
 if (defined $i_lnn) {
   print qq{\$ra[$i_lnn] == lowest natural number $ra[$i_lnn]};
   }
 else {
   print 'no lowest natural number in array';
   }
"
$ra[2] == lowest natural number 4
[download]

Now with more fraction rejection. Still not to be preferred, in very general terms, to an O(n) solution IMHO. Still returns the lowest index of multiple LNNs (update: but a small change will return the highest). (I've started referring to these numbers as "lowest natural numbers" in deference to the N-pairs in the pack/unpack templates.) If you object to all the evaluations of  $ra[$_] in the first map statement, try
    map { my $e = $ra[$_];  $e >= 0 && $e == int($e) ? pack('N N', $e, $_) : () }
instead (tested), but I doubt there'll be much difference.

Update 1: Of course, this will only handle natural numbers in the range of a 32-bit N template specifier. 64-bit Perls have 64-bit Q specifiers. (Update: johngg points out that a big-end enforced Q> (note > modifier) is necessary for proper GRT sorting. I can't test this ATM.)

Update 2: Here's another, semi-tested variation to play around with:
    map $ra[$_] >= 0 && $ra[$_] == int($ra[$_]) && pack('N N', $ra[$_], $_) || (),