If you will only look up one value against the list, or if the list will vary between lookups, then the linear search will be the best solution.

But if your list remains static, and you need to compare more than one value against it, it wouldn't take many linear searches before the cost of sorting the static list and performing a binary chop to locate the nearest two values and then determining the minimum offset between the two would be amortised and begin to pay dividends.

If you need code for this, speak up:)

I was reading your posts in about binary trees, but i can't figure out how to read those (crazy golf solutions :-)). Any chance you might show us the light? :-) I searched using the super search with no luck.

___________
Eric Hodges

Those are for building binary trees, which wouldn't really suit your purpose. There are amost certainly one (or more) modules on CPAN that would provide for binary searching a sorted array, but the usual pattern for these is that they return undef or -1 to indicate that the target value wasn't found, whereas you want to retrieve the index of the nearest lower value so that you can then perform your differencing between the target value and the two nearest. Ie. The values at the index returned and that index +1.

Here's some code that will do that. Note I didn't need to sort my test array as it is already sorted.

#! perl -slw
use strict;

sub bsearch {
    my( $aref, $value ) = @_;
    my( $lo, $hi, $mid ) = ( 0, $#{ $aref } );

    while( $lo <= $hi ) {
        $mid = int( ($lo + $hi) / 2 );
        if(    $value > $aref->[ $mid ] ) {
            $lo = $mid + 1;
        }
        elsif( $value < $aref->[ $mid ] ) {
            $hi = $mid - 1;
        }
        else {
            #Found an exact match so return that index
            return $mid;
        }
     }
    # Didn't find an exact match so return the index below where we st
+opped
    # Or if the value is lower than the 
      # lowest element, return 0
    return $aref->[ $mid ] > $value ? $mid - 1 : $mid;
}


my @array = 0 .. 100;

my $iNearest = bsearch \@array, 31.5;

print 31.5, ' : ', $iNearest, ' : ',$array[ $iNearest ];

print "$_ => @{[ bsearch \@array, $_  ]}" 
    for -1, 0, 1, 2, 31.1, 31.999, 50, 98, 99, 100, 101;

__END__
P:\test>bsearch
31.5 : 31 : 31
-1 => 0
0 => 0
1 => 1
2 => 2
31.1 => 31
31.999 => 31
50 => 50
98 => 98
99 => 99
100 => 100
101 => 100
[download]

You could also code this using a recursive algorithm, but I tend to avoid recursion if the iterative solution doesn't require me to maintain my own stack.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller