note 39115 added to function.array-search
| From: | dennis dot decoene at removthis dot moveit dot be | Date: | Sat, 17 Jan 2004 15:41:26 +0000 |
| Subject: | note 39115 added to function.array-search | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-63738@lists.php.net to get a copy of this message | ||
It has been said before: array_search is VERY slow. Everyone knows binary search is fast by design.
Here is an implementation.
<?php
$arr=array(1,3,5,7,9,10,11,13);
$searchfor = 6;
echo binsearch($searchfor, $arr);
/**
* @return integer
* @param var $needle
* @param array $haystack
* @desc Feed a sorted array to $haystack and a value to search for to $needle.
It will return false if not found or the index where it was found.
This function is superfast. Try an array with 50.000 elements and search for something,
you will be amazed.
*/
function binsearch($needle, $haystack)
{
$high = count($haystack);
$low = 0;
while ($high - $low > 1){
$probe = ($high + $low) / 2;
if ($haystack[$probe] < $needle){
$low = $probe;
}else{
$high = $probe;
}
}
if ($high == count($haystack) || $haystack[$high] != $needle) {
return false;
}else {
return $high;
}
}
?>
----
Manual Page -- http://www.php.net/manual/en/function.array-search.php
Edit -- http://master.php.net/manage/user-notes.php?action=edit+39115
Delete -- http://master.php.net/manage/user-notes.php?action=delete+39115&report=yes
Reject -- http://master.php.net/manage/user-notes.php?action=reject+39115&report=yes
Search -- http://master.php.net/manage/user-notes.php