Have genuinely searched for a solution (I am aware similar has been asked) and tried to understand in 'English' how to think of the code.
I want to find the closest number in an array given a certain number; the code below is what i have thus far.
//Array of numbers
$haystack = array(1,4,67,34,12,76,6,8,45,2);
//Number which we are finding the closest
$needle = 4;
sort($haystack);
foreach($haystack as $number){
if($number > $needle){
$difference = array($number-$needle);
$smallest_num = array_shift($difference);
echo $smallest_num.", "; //Echos out 2, 4, 8, 30, 41, 63, 72,
}
}
Thanks in advanced.
Binary search looks like a good candidate for this case.
It's a bit more complicated than that (e.g. you have 1,5,6 and you are looking for 4. You look at 5 and take the left half, which is 1. That means that you have to go back and take 5, because it's closer), but you should be able to use it as a base algorithm.
The simplest function I came up with (it keeps splitting the array until it reached the nearest numbers up and down the $needle and then finally compares the two.
function findClosest($needle, array $haystack) {
sort($haystack);
$b = 0; // bottom
$u = count($haystack) - 1; // up
while ($u - $b > 1) {
$m = round(($b + $u) / 2);
if ($haystack[$m] < $needle) $b = $m;
else $u = $m;
}
$x = $haystack[$b];
$y = $haystack[$u];
return (($needle-$x) > ($y-$needle)) ? $y : $x;
}
Example of how the array indices are reduced in an array:
$needle = 7;
$array = array(2, 4, 8, 30, 41, 63, 72);
# loop: [$b..$u]
1 loop: [0..6]
2 loop: [0..3]
3 loop: [0..2]
4 loop: [1..2]
Now we know $haystack[1] is just below $needle and $haystack[2] is just above $needle. The script will then make this evaluation:
return (7-4 > 8-7) ? 8 : 4;
returning the correct result: 8.
I've found a solution in PHPs docs using the levenshtein function. By slightly altering the example code, I got it to find the closest number in a sorted array. The function is also relatively quick compared to other similar PHP functions.
<?php
function findClosest($input = 0){
// array of numbers to check against
$numbers = array(4,7,10,15,
1,2,666,1234);
sort($numbers);
// no shortest distance found, yet
$shortest = -1;
// loop through numbers to find the closest
foreach ($numbers as $num) {
// calculate the distance between the input num,
// and the current num
$lev = levenshtein($input, $num);
// check for an exact match
if ($lev == 0) {
// closest num is this one (exact match)
$closest = $num;
$shortest = 0;
// break out of the loop; we've found an exact match
break;
}
// if this distance is less than the next found shortest
// distance, OR if a next shortest num has not yet been found
if ($lev <= $shortest || $shortest < 0) {
// set the closest match, and shortest distance
$closest = $num;
$shortest = $lev;
}
}
echo "Closest number is: " . $closest;
}
?>
I hope this helps, Adam.
Here's a little function I came up with using usort to return the the entire Haystack, sorted by closeness to the Needle. The example I provided after the function should echo 77. (Sorry if it's a little over-commented, I like my documentation to be idiot-proof.)
// Sorts the array by closest to given number
function Find_Closest($Haystack, $Needle)
{
$GLOBALS['Needle'] = $Needle; // allows $Needle to be accessible inside Compare()
// Comparison function used by usort() to determine which number is closest to the needle
if(!function_exists('Reviews_By_Date_Published')) // Only declare function if it hasn't already been declared
{
function Compare($A, $B)
{
global $Needle;
$DistanceB = abs($B - $Needle);
$DistanceA = abs($A - $Needle);
return($DistanceA - $DistanceB);
}
}
usort($Haystack, 'Compare'); // Sorts the Haystack by closest to Needle, using Compare()
return $Haystack;
}
// Example:
$ArrayInQuestion = array(3,4,8,3,6,77,3,5,85,1,24,3);
$SortedArray = Find_Closest($ArrayInQuestion, 76);
$Closest = $SortedArray[0];
echo "Closest = $Closest";
Just take care, my function assumes the arrays are actually arrays and not some other data type.