Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^3: find closest element of array without going over

by starbolin (Hermit)
on Jun 27, 2008 at 00:24 UTC ( #694299=note: print w/replies, xml ) Need Help??


in reply to Re^2: find closest element of array without going over
in thread find closest element of array without going over

Except I see at least five errors in your code.

  • First, your code finds the next element 'greater' than the input not 'ge'. Also it returns the index not the value ( See 'Fourth' below )
  • Second,
    my $tmp = ($right+$left) / 2; if ($a[$tmp] > $search_for){ ...
    Very interesting indexing into an array with a float. I know perl will DWIM but although perl will round toward 0, I don't think it's guaranteed.
  • Third, $right+$left will overflow silently for numbers greater than 1e31 on many systems. This is a rare occurrence in these days of 32 bit int but it's there nevertheless.
  • Fourth, your code returns an empty list element if $search_for is at the end of the array. While this my be a usefull error return, should the programmer attempt to use the index to retrieve a value from the array, the program would break.
  • Fifth, in your example you define your array to be one larger than what you search over. While this is more an implementation problem than an algorithm problem the example is nonetheless in error.
  • I'm being picky here because the code illustrates that a quick-search is difficult to write correctly. Your code makes my point perfectly, thank you.

    Update: Three is a Red Herring. When first I looked at your code I said "Ah, there is the Binary-Search-Overflow bug!" But of course this was a bigger problem when long was the memory space and int was shorter than long. But Perl is written so that an int can access the total memory space and so three is less of a bug that any other operation on large integers would be.


    s//----->\t/;$~="JAPH";s//\r<$~~/;{s|~$~-|-~$~|||s |-$~~|$~~-|||s,<$~~,<~$~,,s,~$~>,$~~>,, $|=1,select$,,$,,$,,1e-1;print;redo}

    Log In?
    Username:
    Password:

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

    How do I use this? | Other CB clients
    Other Users?
    Others having an uproarious good time at the Monastery: (5)
    As of 2022-09-27 05:43 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      I prefer my indexes to start at:




      Results (118 votes). Check out past polls.

      Notices?