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

Find a matching or closest value in an array

提问by FMaz008

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。

回答by Tim Cooper

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

回答by mario

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

回答by Peter

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_DEFAULTfinds nearest element
• ARRAY_NEAREST_LOWERfinds nearest element which is LOWER
• ARRAY_NEAREST_HIGHERfinds nearest element which is HIGHER

• ARRAY_NEAREST_DEFAULT找到最近的元素
• ARRAY_NEAREST_LOWER找到最近的 LOWER 元素
• 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);

回答by Wrikken

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

回答by RobertPitt

You can simply use array_searchfor 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，则返回第一个匹配的键。要返回所有匹配值的键，请改用array_keys()和可选的 search_value 参数。

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

回答by Gajus

Tim's implementationwill 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.

大多数时候，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] );
}

回答by quantme

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

要在对象数组中搜索最近的值，您可以使用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://stackoverflow.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);
?>

回答by k to the z

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.

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

回答by llange

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

回答by Rohan

Try these.. this not only gives the nearest matching but provides both the nearest higher value and the nearest lower value than a given number.

试试这些……这不仅给出了最接近的匹配，而且还提供了与给定数字最接近的较高值和最接近的较低值。

 getNearestValue(lookup_array, lookup_value) {

        if (lookup_array.length > 0) {
          let nearestHighValue = lookup_array[0];
          let nearestLowValue = lookup_array[0];
          let nearestValue=0;
          let diff, diffPositive = Infinity;
          let diffNeg = -Infinity;
          lookup_array.forEach(num => {
            diff = lookup_value - num;
            if (diff >= 0 && diff <= diffPositive) {
              nearestLowValue = num;
              diffPositive = diff;
            }
            if (diff <= 0 && diff >= diffNeg) {
              nearestHighValue = num;
              diffNeg = diff;
            }

          })
          //If no value is higher than GivenNumber then  keep nearest low value as clossets
          if (diffNeg == -Infinity) {
            nearestHighValue = nearestLowValue;
          }
              //If no value is Lower than Givennumber then  keep nearest High value as clossets
          if (diffPositive == Infinity) {
            nearestLowValue = nearestHighValue;
          }
          if((lookup_value-nearestLowValue)<=(nearestHighValue-lookup_value))
            {
              nearestValue=nearestLowValue;
             }
         else
            {
            nearestValue=nearestHighValue;
            }
          return { NearHighest: nearestHighValue, NearLowest: nearestLowValue,NearestValue:nearestValue };
        }
        else {
          return null;
        }
      }