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

How can I search and find, for a given target value, the closest value in an array?

对于给定的目标值，如何搜索和查找数组中最接近的值？

Let's say I have this exemplary array:

假设我有这个示例性数组：

array(0, 5, 10, 11, 12, 20)

For example, when I search with the target value 0, the function shall return 0; when I search with 3, it shall return 5; when I search with 14, it shall return 12.

例如，当我用目标值0搜索时，函数应返回0;当我用3搜索时，它将返回5;当我用14搜索时，它将返回12。

10 个解决方案

#1

Pass in the number you're searching for as the first parameter and the array of numbers to the second:

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

function getClosest($search, $arr) {
   $closest = null;
   foreach ($arr as $item) {
      if ($closest === null || abs($search - $closest) > abs($item - $search)) {
         $closest = $item;
      }
   }
   return $closest;
}

#2

A particular lazy approach is having PHP sort the array by the distance to the searched number:

一种特殊的懒惰方法是让PHP按照搜索到的数字的距离对数组进行排序：

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

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

#3

This is high-performance function I wrote for sorted big arrays

这是我为排序的大数组编写的高性能函数

Tested, main loop needs only ~20 iterations for an array with 20000 elements.

对于具有20000个元素的数组，经过测试的主循环仅需要~20次迭代。

Please mind array has to be sorted (ascending)!

请注意数组必须排序（升序）！

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 finds nearest element
• ARRAY_NEAREST_DEFAULT查找最近的元素
• ARRAY_NEAREST_LOWER finds nearest element which is LOWER
• ARRAY_NEAREST_LOWER查找最近的元素，即LOWER
• ARRAY_NEAREST_HIGHER finds nearest element which is HIGHER
• ARRAY_NEAREST_HIGHER找到最接近的元素

Usage:

用法：

$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);

#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);
}
?>

#5

You can simply use array_search for that, it returns one single key, if there are many instances of your search found within the array, it would return the first one it finds.

您可以简单地使用array_search，它返回一个单独的键，如果在数组中找到了很多搜索实例，它将返回它找到的第一个实例。

Quote from PHP:

从PHP引用：

If needle is found in haystack more than once, the first matching key is returned. To return the keys for all matching values, use array_keys() with the optional search_value parameter instead.

如果在haystack中多次找到needle，则返回第一个匹配的键。要返回所有匹配值的键，请使用带有可选search_value参数的array_keys（）。

Example Usage:

用法示例：

if(false !== ($index = array_search(12,array(0, 5, 10, 11, 12, 20))))
{
    echo $index; //5
}

---

Update:

更新：

function findNearest($number,$Array)
{
    //First check if we have an exact number
    if(false !== ($exact = array_search($number,$Array)))
    {
         return $Array[$exact];
    }

    //Sort the array
    sort($Array);

   //make sure our search is greater then the smallest value
   if ($number < $Array[0] ) 
   { 
       return $Array[0];
   }

    $closest = $Array[0]; //Set the closest to the lowest number to start

    foreach($Array as $value)
    {
        if(abs($number - $closest) > abs($value - $number))
        {
            $closest = $value;
        }
    }

    return $closest;
}

#6

Tim's implementation will cut it most of the time. Nevertheless, for the performance cautious, you can sort the list prior to the iteration and break the search when the next difference is greater than the last.

蒂姆的实施将大部分时间削减它。尽管如此，为了保持性能谨慎，您可以在迭代之前对列表进行排序，并在下一个差异大于最后一个差异时中断搜索。

<?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] );
}

#7

To search the nearest value into an array of objects you can use this adapted code from Tim Cooper's answer.

要将最近的值搜索到一个对象数组中，您可以使用Tim Cooper的答案中的这个改编代码。

<?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://*.com/a/5464961/496176
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);
?>

#8

function closestnumber($number, $candidates) {
$last = null;
foreach ($candidates as $cand) {
    if ($cand < $number) {
        $last = $cand;
    } else if ($cand == $number) {
        return $number;
    } else if ($cand > $number) {
        return $last;
    }
}
return $last;
}

This should get you what you need.

这应该可以满足您的需求。

#9

Considering that the input array is sorted in ascending order asort() for example, you'll be far faster to search using a dichotomic search.

例如，考虑到输入数组按升序asort（）排序，使用二分搜索进行搜索的速度要快得多。

Here's a quick and dirty adaptation of some code I'm using to insert a new event in an Iterable event list sorted by DateTime objects…

这是一个快速而肮脏的改编，我正在使用一些代码在一个按DateTime对象排序的Iterable事件列表中插入一个新事件...

Thus this code will return the nearest point at the left (before / smaller).

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

If you'd like to find the mathematically nearest point: consider comparing the distance of the search value with the return value and the point immediately at the right (next) of the return value (if it exists).

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

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);        
}

#10

try this: (it has not been tested)

试试这个:(它还没有经过测试）

function searchArray($needle, $haystack){
    $return = $haystack[0];
    $prevReturn = $return;
    foreach($haystack as $key=>$val){
         if($needle > $val) {
            $prevReturn = $return;
            $return = $val;
         }
         if($val >= $needle) {
            $prevReturn = $return;
            $return = $val;
            break;
         }
    }
    if((($return+$needle)/2) > (($prevReturn+$needle)/2)){
         //means that the needle is closer to $prevReturn
         return $prevReturn;
    }
    else return $return;
}