note 39115 deleted from function.array-search by cmb
| From: | cmb@php.net | Date: | Sun, 05 Jan 2020 08:20:29 +0000 |
| Subject: | note 39115 deleted from function.array-search by cmb | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-213749@lists.php.net to get a copy of this message | ||
Note Submitter: dennis dot decoene at removthis dot moveit dot be
----
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;
}
}
?>