Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: searching a list

by esskar (Deacon)
on Jun 27, 2006 at 13:05 UTC ( #557786=note: print w/ replies, xml ) Need Help??


in reply to searching a list

searching a list, i always like binary search. of course, the list has to be sorted tough. here is a little script

use strict; use warnings; my @s = ( 'abc', 'dog', 'cat', 'rabbit', 'attic' ); my @sorted_copy = sort { $a cmp $b } @s; print ' at:' . contains_string( 'at', \@sorted_copy ) . "\n"; print 'cat:' . contains_string( 'cat', \@sorted_copy ) . "\n"; sub contains_string { my ( $var, $array ) = @_; return binary_string_search( $var, $array ) > -1; } sub binary_string_search { my ( $var, $array, $lo, $hi ) = @_; $lo = 0 unless defined $lo; $hi = $#{ @{$array} } unless defined $hi; while ( $lo <= $hi ) { # determine new division point my $mid = $lo + int( ( $hi - $lo ) / 2 ); if ( $array->[$mid] eq $var ) { return $mid; } elsif ( $var le $array->[$mid] ) { $hi = $mid - 1; } else { $lo = $mid + 1; } } # nothing found return -1; }
i think you can achieve a speedy solution when searching a big list for more than one item.

UPDATE: minor code changes.


Comment on Re: searching a list
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://557786]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (10)
As of 2014-08-28 10:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (259 votes), past polls