PHP查找给定$haystack和$needle的最接近的数字

Question

我诚心诚意地寻找解决方案(我知道有人问过类似的问题)，并试图用“英语”来理解如何思考代码。

我想在给定某个数字的数组中找到最接近的数字；下面的代码就是到目前为止我所拥有的代码。

//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,
    }
}

在进阶时谢谢。

Answer 1

对于这种情况，Binary search看起来是一个很好的候选者。

这要复杂得多(例如，你有1,5,6，你正在寻找4。你看看5，然后取左半部分，也就是1，这意味着你必须返回并取5，因为它更接近)，但你应该能够使用它作为基础算法。

Answer 2

我想出的最简单的函数(它不断拆分数组，直到它在$needle上上下达到最接近的数字，然后最后比较这两个数字。

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;

}

如何在数组中减少数组索引的示例：

$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]

现在我们知道$haystack[1]在$needle之下，$haystack[2]在$needle之上。然后，该脚本将进行以下评估：

return (7-4 > 8-7) ? 8 : 4;

返回正确结果：8。

Answer 3

这是我想出的一个小函数，使用usort返回整个干草堆，按与针的距离排序。我在函数后面提供的示例应该回显77。(抱歉，如果有一点评论过度了，我喜欢我的文档是傻瓜式的。)

// 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";

请注意，我的函数假定数组实际上是数组，而不是其他数据类型。