Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: “A meeting at the Liquor-Vodka Factory”, or… same ARRAY questions again?!!

by graff (Chancellor)
on Sep 02, 2005 at 21:59 UTC ( #488801=note: print w/replies, xml ) Need Help??


in reply to “A meeting at the Liquor-Vodka Factory”, or… same ARRAY questions again?!!

Thank you for an entertaining statement of the problem. I suppose some people might view multiple answers to a question as causing some sort of difficulty, but it is in the spirit of Perl to have multiple ways to perform a task. If you're not comfortable with that, well, you'll get used to it as you spend more time with the language.

Please understand that your closing question is actually different from, in terms of being much more detailed than, the FAQ that you cited. In a perfect world, the more general, less specific nature of the FAQ answers would give you a starting point, and from there you can try tweaks and variations that would isolate and adapt a general approach to your specific need. You do need to do some of the work yourself.

BTW, please please remember that you can use HTML formatting tags (like <UL>, <LI>, etc) in your post. Using <pre> is generally unnecessary and not helpful.

Regarding your last request, I'm reluctant to post a specific solution, because I'm not sure how much error trapping might be called for (e.g. checking for wrong number of args, wrong type of args, array not sorted, array contains undef or non-integer elements, array contains non-unique elements, etc), or what sort of behavior would be best when an error is caught (e.g. die, croak, carp, or just return a non-integer, given that an undef return is supposed to be a valid result). These things depend on how much is known, or not known, about the caller.

And of course, as indicated an earlier reply, what is known (or not known) about the caller and the input data will make a difference in what sort of algorithm is best.

I suppose if I change your spec, it might be easier for the sub to be written in a more adaptable way: return undef in case the inputs to the sub fail to meet any essential condition; return "-1" if the inputs are considered valid and the target does not occur in the array; otherwise, return an index pointing to the target value in the array.

Since this reply is already too long, I'll take the shortcut of assuming that the inputs can be trusted to meet the stated conditions:

sub find_int_in_array { my ( $arref, $targ ) = @_; # args are array ref, int value my $asize = scalar @$arref; my $lasta = $asize - 1; my $result = ( $targ < $$arref[0] or $targ > $$arref[$lasta] ) ? - +1 : ( $targ == $$arref[$lasta] ) ? $lasta : ( $targ == $$arref[0] ) ? 0 : undef; return $result if ( defined( $result )); my $nextidx = $asize / 2; my $nextinc = $nextidx / 2; while ( ! defined( $result )) { if ( $$arref[$nextidx] == $targ ) { $result = $nextidx; } else { my $newidx = ( $$arref[$nextidx] < $targ ) ? $nextidx + $nextinc : $nextidx - $nextinc; $result = -1 if ( $nextidx == $newidx ); $nextidx = $newidx; $nextinc /= 2; } } return $result; }
If you want to add some error checking to that, just have it return undef when there is an error. Or better yet, use a module that already exists to do a binary search over an array (as cited in the first reply) and read its man page.
  • Comment on Re: “A meeting at the Liquor-Vodka Factory”, or… same ARRAY questions again?!!
  • Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (3)
As of 2023-02-09 02:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (44 votes). Check out past polls.

    Notices?