note 105865 added to function.array-search

It seems like there's a small bug in temporal dot pl at gmail's Array_BinarySearch() function (thanks for posting it, BTW). I have found that sometimes the $probe that gets returned is where the item should be inserted and sometimes it's the item just before it should be inserted. Here's a use case that illustrates the issue: <?php $haystack = array( "a", "b", "c", "d", "e"); $needle = "ca"; $res = Array_BinarySearch( $needle, $haystack, 'strcmp', $probe); echo (int)$res . ' ' . $probe . '<br />'; // output is: 0 3 -- thinks it should be inserted at position 3 = GOOD $needle = "bb"; $res = Array_BinarySearch( $needle, $haystack, 'strcmp', $probe); echo (int)$res . ' ' . $probe . '<br />'; // output is: 0 1 -- thinks it should be inserted at position 1 = BAD ?> If we output the values for each High, Low, Probe, and Comparison for each round we get: H: 4, L: 0, P: 2, C: < H: 4, L: 3, P: 3, C: > res: 0, probe: 3 H: 4, L: 0, P: 2, C: > H: 1, L: 0, P: 0, C: < H: 1, L: 1, P: 1, C: < res: 0, probe: 1 So, in order to handle this last case where "bb" should actually be inserted in position 2, I've modified the function to have a different comparison: <?php function Array_BinarySearch( $needle, $haystack, $comparator , &$probe ) { $high = Count( $haystack ) -1; $low = 0; while ( $high >= $low ) { $probe = Floor( ( $high + $low ) / 2 ); $comparison = $comparator( $haystack[$probe], $needle ); if ( $comparison < 0 ) { $low = $probe +1; } elseif ( $comparison > 0 ) { $high = $probe -1; } else { return true; } } //The loop ended without a match // Adjust probe if it > than currently indexed value if ($comparator($needle, $haystack[$probe]) > 0) { $probe++; } return false; } ?> This comparison also handles the case where the found element would end up being after the last element. Running with a needle of "zz" produces a probe value of 5: H: 4, L: 0, P: 2, C: < H: 4, L: 3, P: 3, C: < H: 4, L: 4, P: 4, C: < res: 0, probe: 5 ---- Server IP: 208.69.120.55 Probable Submitter: 204.15.240.18 ---- Manual Page -- http://www.php.net/manual/en/function.array-search.php Edit -- https://master.php.net/note/edit/105865 Del: integrated -- https://master.php.net/note/delete/105865/integrated Del: useless -- https://master.php.net/note/delete/105865/useless Del: bad code -- https://master.php.net/note/delete/105865/bad+code Del: spam -- https://master.php.net/note/delete/105865/spam Del: non-english -- https://master.php.net/note/delete/105865/non-english Del: in docs -- https://master.php.net/note/delete/105865/in+docs Del: other reasons-- https://master.php.net/note/delete/105865 Reject -- https://master.php.net/note/reject/105865 Search -- https://master.php.net/manage/user-notes.php