note 93352 added to function.array-search

Sometimes you need to find a given value in a sorted array or - if not found - detect the place where it should be. After that you can for example split the array into two halves, the greater and the smaller one. greenmr, dennis.decoene and php at celerondude had all posted very good binary search functions but these functions all return false if the needle was not found in the haystack. I've tweaked greenmr's code a little: <?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 //Compensate for needle greater than highest haystack element if($comparator($haystack[count($haystack)-1], $needle) < 0) { $probe = count($haystack); } return false; } ?> Now, the function returns true if it finds something and false otherwise. If a needle was found, then $probe will contain it's position. Otherwise, $probe will contain position of where the needle would be if it were there :). This is possible because we pass $probe by reference. Example: <?php //ultra-simple comparator :) function CompareNumbers($obj, $needle) { return $obj - $needle; } //use examples $testArr = array(10, 20, 30, 40, 50); $res = Array_BinarySearch(30, $testArr, 'CompareNumbers', $probe); echo (int)$res.' '.$probe.'<br />'; //output is: 1 2 - found at position 2 $res = Array_BinarySearch(45, $testArr, 'CompareNumbers', $probe); echo (int)$res.' '.$probe.'<br />'; //output is: 0 4 - not found, but it would be at position 4 (between 40 and 45) $res = Array_BinarySearch(-3, $testArr, 'CompareNumbers', $probe); echo (int)$res.' '.$probe.'<br />'; //output is: 0 0 - not found, but it would be at position 0 (before 10) $res = Array_BinarySearch(300, $testArr, 'CompareNumbers', $probe); echo (int)$res.' '.$probe.'<br />'; //output is: 0 5 - not found, but it would be at position 5 (after 50; note, that count($haystack) == 5) ?> See original greenmr's note for additional details about usage of this binary search: http://php.net/manual/en/function.array-search.php#89413 ---- Server IP: 82.177.164.100 Probable Submitter: 81.190.111.151 ---- Manual Page -- http://www.php.net/manual/en/function.array-search.php Edit -- https://master.php.net/note/edit/93352 Del: integrated -- https://master.php.net/note/delete/93352/integrated Del: useless -- https://master.php.net/note/delete/93352/useless Del: bad code -- https://master.php.net/note/delete/93352/bad+code Del: spam -- https://master.php.net/note/delete/93352/spam Del: non-english -- https://master.php.net/note/delete/93352/non-english Del: in docs -- https://master.php.net/note/delete/93352/in+docs Del: other reasons-- https://master.php.net/note/delete/93352 Reject -- https://master.php.net/note/reject/93352 Search -- https://master.php.net/manage/user-notes.php