note 93704 deleted from function.array-search by danbrown
| From: | danbrown@php.net | Date: | Wed, 23 Sep 2009 17:22:59 +0000 |
| Subject: | note 93704 deleted from function.array-search by danbrown | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-160988@lists.php.net to get a copy of this message | ||
Note Submitter: bluej100@gmail
----
@temporal
There's a slight error in your otherwise excellent binary search: you need to correct the probe
whenever it ends on a lesser value, not just when it ends on the last element. Here's my
version and tests:
<?php
function array_bisearch($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[$probe], $needle) < 0) {
$probe++;
}
return false;
}
$needles = array('ab', 'b', 'd');
foreach (array(array('a', 'ab', 'b ', 'ba', 'bb'),
array('a', 'ab', 'ca', 'cb')) as $haystack) {
sort($haystack);
echo 'Haystack:';
var_dump($haystack);
foreach ($needles as $needle) {
echo 'Needle: ';
var_dump($needle);
array_bisearch($needle, $haystack, 'strcmp', $probe);
if (isset($haystack[$probe])) {
var_dump($haystack[$probe]);
} else {
echo "FAIL\n";
}
}
}
?>