Re^3: 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){ ...
[download]

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}

Comment on Re^3: find closest element of array without going over Download Code


Think about Loose Coupling
	PerlMonks