logo标签列表

在数组中查找匹配或最接近的值

phparrayssearchsorting
76

如何在数组中搜索并找到最接近给定目标值的值？

假设我有以下示例数组：

array(0, 5, 10, 11, 12, 20)
例如，当我使用目标值0进行搜索时，该函数应返回0；当我使用3进行搜索时，它应返回5；当我使用14进行搜索时，它应返回12。
13个回答
141

将您搜索的数字作为第一个参数传入，将数字数组作为第二个参数传入：

function getClosest($search, $arr) {
   $closest = null;
   foreach ($arr as $item) {
      if ($closest === null || abs($search - $closest) > abs($item - $search)) {
         $closest = $item;
      }
   }
   return $closest;
}
2
这里需要补充的一点是，如果你想要比搜索值更接近的较小值，你需要按升序对数组进行排序；否则，按降序排序以获得比搜索值更接近的较大值。 - Sandip Karanjekar
2
抱歉打扰这个旧回答，但如果使用负数，我似乎遇到了问题，有什么建议吗？ - webaholik
我认为应该使用abs($search - $closest) >= abs($item - $search)来将数字四舍五入到最接近的值。 - Sos.
有人知道 $closest === null 是什么意思吗？ - Robert Sinclair
1
@RobertSinclair $closest === null 是用于第一次迭代之前，因为此时 closest 还没有被设置为任何值。 - Andy
20

一种常见的懒惰方法是让PHP根据与搜索数字的距离对数组进行排序：

$num = 3;    
$array = array(0, 5, 10, 11, 12, 20);
$smallest = [];

foreach ($array as $i) {
    $smallest[$i] = abs($i - $num);
}
asort($smallest);
print key($smallest);
17

我为大数组排序编写了高性能函数。

测试表明，对于一个包含20000个元素的数组，主循环只需要约20次迭代。

请注意数组必须是按升序排列的！

define('ARRAY_NEAREST_DEFAULT',    0);
define('ARRAY_NEAREST_LOWER',      1);
define('ARRAY_NEAREST_HIGHER',     2);

/**
 * Finds nearest value in numeric array. Can be used in loops.
 * Array needs to be non-assocative and sorted.
 * 
 * @param array $array
 * @param int $value
 * @param int $method ARRAY_NEAREST_DEFAULT|ARRAY_NEAREST_LOWER|ARRAY_NEAREST_HIGHER
 * @return int
 */
function array_numeric_sorted_nearest($array, $value, $method = ARRAY_NEAREST_DEFAULT) {    
    $count = count($array);

    if($count == 0) {
        return null;
    }    

    $div_step               = 2;    
    $index                  = ceil($count / $div_step);    
    $best_index             = null;
    $best_score             = null;
    $direction              = null;    
    $indexes_checked        = Array();

    while(true) {        
        if(isset($indexes_checked[$index])) {
            break ;
        }

        $curr_key = $array[$index];
        if($curr_key === null) {
            break ;
        }

        $indexes_checked[$index] = true;

        // perfect match, nothing else to do
        if($curr_key == $value) {
            return $curr_key;
        }

        $prev_key = $array[$index - 1];
        $next_key = $array[$index + 1];

        switch($method) {
            default:
            case ARRAY_NEAREST_DEFAULT:
                $curr_score = abs($curr_key - $value);

                $prev_score = $prev_key !== null ? abs($prev_key - $value) : null;
                $next_score = $next_key !== null ? abs($next_key - $value) : null;

                if($prev_score === null) {
                    $direction = 1;                    
                }else if ($next_score === null) {
                    break 2;
                }else{                    
                    $direction = $next_score < $prev_score ? 1 : -1;                    
                }
                break;
            case ARRAY_NEAREST_LOWER:
                $curr_score = $curr_key - $value;
                if($curr_score > 0) {
                    $curr_score = null;
                }else{
                    $curr_score = abs($curr_score);
                }

                if($curr_score === null) {
                    $direction = -1;
                }else{
                    $direction = 1;
                }                
                break;
            case ARRAY_NEAREST_HIGHER:
                $curr_score = $curr_key - $value;
                if($curr_score < 0) {
                    $curr_score = null;
                }

                if($curr_score === null) {
                    $direction = 1;
                }else{
                    $direction = -1;
                }  
                break;
        }

        if(($curr_score !== null) && ($curr_score < $best_score) || ($best_score === null)) {
            $best_index = $index;
            $best_score = $curr_score;
        }

        $div_step *= 2;
        $index += $direction * ceil($count / $div_step);
    }

    return $array[$best_index];
}
  • ARRAY_NEAREST_DEFAULT：查找最近的元素。
  • ARRAY_NEAREST_LOWER：查找最近且小于给定值的元素。
  • ARRAY_NEAREST_HIGHER：查找最近且大于给定值的元素。

用法：

$test = Array(5,2,8,3,9,12,20,...,52100,52460,62000);

// sort an array and use array_numeric_sorted_nearest
// for multiple searches. 
// for every iteration it start from half of chunk where
// first chunk is whole array
// function doesn't work with unosrted arrays, and it's much
// faster than other solutions here for sorted arrays

sort($test);
$nearest = array_numeric_sorted_nearest($test, 8256);
$nearest = array_numeric_sorted_nearest($test, 3433);
$nearest = array_numeric_sorted_nearest($test, 1100);
$nearest = array_numeric_sorted_nearest($test, 700);
@MjrKusanagi array_numeric_sorted_nearest 是主要函数，但在使用它之前需要对数组进行排序。 - Peter
这个函数有很多漏洞，在运行各种测试用例时，会在索引上遇到一些偏差问题。(例如测试数据：$array = [1, 5, 10]; $value = 2 或者 $array = [0.34, 0.5, 0.9, 1.9, 18.6]; $value = 0.89) - calumbrodie
@calumbrodie，你的测试用例在这里看起来运行良好！ - Pepijn Olivier
2
请注意，此功能不能在PHP7上开箱即用，因为当数组索引缺失时会抛出错误。您必须添加适当的isset检查。 - Pepijn Olivier
5
我已经将这段代码升级为符合PHP7标准的版本，可以在这个gist链接中找到。 - Pepijn Olivier
显示剩余2条评论
4
<?php
$arr = array(0, 5, 10, 11, 12, 20);

function getNearest($arr,$var){
    usort($arr, function($a,$b) use ($var){
        return  abs($a - $var) - abs($b - $var);
    });
    return array_shift($arr);
}
?>
可能会起作用，但需要比TimCooper更多的处理。 - FMaz008
能用，但我认为Tim的代码需要更少的循环。 - Wrikken
2

基于Piyush Dholariya的回答，我找到的最佳方法如下：

$array = [4, 9, 15, 6, 2];
$goal = 7;

$closest = array_reduce($array, function($carry, $item) use($goal) {
    return (abs($item - $goal) < abs($carry - $goal) ? $item : $carry);
}, reset($array)); // Returns 6
1

要在对象数组中搜索最近的值，您可以使用从Tim Cooper's answer改编的代码。

<?php
// create array of ten objects with random values
$images = array();
for ($i = 0; $i < 10; $i++)
    $images[ $i ] = (object)array(
        'width' => rand(100, 1000)
    );

// print array
print_r($images);

// adapted function from Tim Copper's solution
// https://dev59.com/im035IYBdhLWcg3wW-z1#5464961
function closest($array, $member, $number) {
    $arr = array();
    foreach ($array as $key => $value)
        $arr[$key] = $value->$member;
    $closest = null;
    foreach ($arr as $item)
        if ($closest === null || abs($number - $closest) > abs($item - $number))
            $closest = $item;
    $key = array_search($closest, $arr);
    return $array[$key];
}

// object needed
$needed_object = closest($images, 'width', 320);

// print result
print_r($needed_object);
?>
1

Tim的实现在大多数情况下都可以胜任。然而，对于那些注重性能的人来说，在迭代之前对列表进行排序，并在下一个差异大于上一个差异时停止搜索，是一种更好的选择。

<?php
function getIndexOfClosestValue ($needle, $haystack) {
    if (count($haystack) === 1) {
        return $haystack[0];
    }

    sort($haystack);

    $closest_value_index = 0;
    $last_closest_value_index = null;

    foreach ($haystack as $i => $item) {
        if (abs($needle - $haystack[$closest_value_index]) > abs($item - $needle)) {
            $closest_value_index = $i;
        }

        if ($closest_value_index === $last_closest_value_index) {
            break;
        }
    }
    return $closest_value_index;
}

function getClosestValue ($needle, $haystack) {
    return $haystack[getIndexOfClosestValue($needle, $haystack)];
}

// Test

$needles = [0, 2, 3, 4, 5, 11, 19, 20];
$haystack = [0, 5, 10, 11, 12, 20];
$expectation = [0, 0, 1, 1, 1, 3, 5, 5];

foreach ($needles as $i => $needle) {
    var_dump( getIndexOfClosestValue($needle, $haystack) === $expectation[$i] );
}
1

这与Mario的答案相同，但我使用array_search()和min()而不是排序。性能相同，所以只是个人偏好的问题。

function findClosest(array $values, $match)
{
    $map = [];
    foreach ($values as $v) {
        $map[$v] = abs($match - $v);
    }
    return array_search(min($map), $map);
}
0

考虑到输入数组是按升序排序的，例如使用asort()，使用二分搜索将更快。

这是我正在使用的一些代码的快速适应，用于在按DateTime对象排序的Iterable事件列表中插入新事件...

因此，此代码将返回左侧（之前/较小）最近的点。

如果您想找到数学上最接近的点：请考虑将搜索值的距离与返回值及其右侧（下一个）点（如果存在）的距离进行比较。

function dichotomicSearch($search, $haystack, $position=false)
{
    // Set a cursor between two values
    if($position === false)
    {    $position=(object)  array(
            'min' => 0,
            'cur' => round(count($haystack)/2, 0, PHP_ROUND_HALF_ODD),
            'max' => count($haystack)
            );
    }

    // Return insertion point (to push using array_splice something at the right spot in a sorted array)
    if(is_numeric($position)){return $position;}

    // Return the index of the value when found
    if($search == $haystack[$position->cur]){return $position->cur;}

    // Searched value is smaller (go left)
    if($search <= $haystack[$position->cur])
    {
        // Not found (closest value would be $position->min || $position->min+1)
        if($position->cur == $position->min){return $position->min;}

        // Resetting the interval from [min,max[ to [min,cur[
        $position->max=$position->cur;
        // Resetting cursor to the new middle of the interval
        $position->cur=round($position->cur/2, 0, PHP_ROUND_HALF_DOWN);
        return dichotomicSearch($search, $haystack, $position);
    }

    // Search value is greater (go right)
        // Not found (closest value would be $position->max-1 || $position->max)
        if($position->cur < $position->min or $position->cur >= $position->max){return $position->max;}
        // Resetting the interval from [min,max[ to [cur,max[
        $position->min = $position->cur;
        // Resetting cursor to the new middle of the interval
        $position->cur = $position->min + round(($position->max-$position->min)/2, 0, PHP_ROUND_HALF_UP);
        if($position->cur >= $position->max){return $position->max;}
        return dichotomicSearch($search, $haystack, $position);        
}
0
function closestnumber($number, $candidates) {
    $last = null;
    foreach ($candidates as $cand) {
        if ($cand < $number) {
            $last = $cand;
        } elseif ($cand == $number) {
           return $number;
        } elseif ($cand > $number) {
           return $last;
        }
    }
    return $last;
}
1
这需要数组值已被排序吗？ - user212218
我认为是这样的，那个函数由于某些原因没有通过我的单元测试（失败了，断言0与期望的5不匹配）。:( - FMaz008
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接