Syntactic Confectionery Delight PerlMonks

### Re: find closest element of array without going over

by jds17 (Pilgrim)
 on Jun 26, 2008 at 18:40 UTC ( #694252=note: print w/replies, xml ) Need Help??

Hi, I am afraid I am reinventing the wheel here, but I had fun writing it, so here it goes. Comments:
1. It's just a binary search, as suggested by everyone else!
2. The performance should be quite good, but I did not test it against big arrays (and I would obviously need to write something to test against...)
3. In case two numbers in the array are equally close, the bigger number will be chosen as the winner.
Update: Of course I have to assume the target array is sorted.
```use strict;
use warnings;

my @array = (1,4,5,6,7,9,10,23,34,44,55,56,57,59,70,80,90,100);

print "\nenter number\n";
chomp (my \$find = <STDIN>);

my \$nearest = @{nearest(\@array)}[0];
print "nearest to \$find in array is: \$nearest\n";

sub nearest {
my (\$a) = @_;
my \$size = @\$a;
return \$a if \$size == 1;
my \$mid = int((\$size-1) / 2);
my \$test = @\$a[\$mid];
return \$test <= \$find ?
(abs(\$test-\$find)<abs(@\$a[\$mid+1]-\$find) ? [\$test] :
\$find <= @\$a[\$mid+1] ? [@\$a[\$mid+1]] : nearest([@\$a[\$mid+1 .. \$
+size-1]]))
:
(abs(\$test-\$find)<abs(@\$a[\$mid-1]-\$find) ? [\$test] :
\$find >= @\$a[\$mid-1] ? [@\$a[\$mid-1]] : nearest([@\$a[0 .. \$mid]]
+));
}

Create A New User
Node Status?
node history
Node Type: note [id://694252]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?