https://bugzilla.wikimedia.org/show_bug.cgi?id=164
--- Comment #218 from Philippe Verdy <verd...@wanadoo.fr> 2011-07-20 08:54:53 UTC --- OK, I immediately found a bug in the binary search function (which is defintely not beinary, has slower than expected convergence, and may even stale on testing the same index, due to incorrect handling of min/max indice after comparing): 291 function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) { 292 $min = 0; 293 $max = $valueCount - 1; 294 do { 295 $mid = $min + ( ( $max - $min ) >> 1 ); 296 $item = call_user_func( $valueCallback, $mid ); 297 $comparison = call_user_func( $comparisonCallback, $target, $item ); 298 if ( $comparison > 0 ) { 299 $min = $mid; 300 } elseif ( $comparison == 0 ) { 301 $min = $mid; 302 break; 303 } else { 304 $max = $mid; 305 } 306 } while ( $min < $max - 1 ); 307 308 if ( $min == 0 && $max == 0 && $comparison > 0 ) { 309 // Before the first item 310 return false; 311 } else { 312 return $min; 313 } 314 } The authout should have better read how TESTED binary searches are implemented. This should really be: function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) { $min = 0; $max = $valueCount - 1; while ( $min <= $max ) { $mid = ($min + $max) >> 1; $item = call_user_func( $valueCallback, $mid ); $comparison = call_user_func( $comparisonCallback, $item, $target ); if ( $comparison < 0 ) { $min = $mid + 1; } elseif ( $comparison > 0 ) { $max = $mid - 1; } else { return $mid; // or: $max = $mid; break; } } // $target not found, now $max < min (more exactly, $max = $min - 1). // $target is to insert between them: $max is the highest lower bound. if ( $max < 0 ) { // Before the first item return false; // Don't test with a simple if ! } else { return $max; // May return 0 (lower bound on first item) } } Note that the final test to return false is unnecessary and causes confusion on usage (if you had written this in C/C++ instead of PHP, you would not be able to make the distinction between false (no lower bound not found) and 0 (valid lower bound). Your code should not depend on those PHP hacks, which consists in returning values of distinct types (but with PHP's implicit promotion on basic types, it's really dangerous do do that) ! It's just simpler to let it return -1 (the content already in $max when we are before the first item), and then let the caller test the negative sign of the result, instead of comparing it then with false. -- Configure bugmail: https://bugzilla.wikimedia.org/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are on the CC list for the bug. _______________________________________________ Wikibugs-l mailing list Wikibugs-l@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/wikibugs-l