note 93352 deleted from function.array-search by cmb
| From: | cmb@php.net | Date: | Sun, 05 Jan 2020 08:21:51 +0000 |
| Subject: | note 93352 deleted from function.array-search by cmb | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-213751@lists.php.net to get a copy of this message | ||
Note Submitter: temporal dot pl at gmail dot com
----
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