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

小开

最佳答案

将您正在搜索的数字作为第一个参数和数组传递给第二个参数:

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

小开

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

小开

一种特殊的惰性方法是让 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);

小开

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

小开

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

引自 PHP :

如果在干草堆中发现针不止一次，则返回第一个匹配的键。若要返回所有匹配值的键，请使用带有可选 search _ value 参数的 Array _ keys ()。

示例用法:

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

更新:

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

小开

这是我为 分类的大数组编写的高性能函数

经过测试，对于包含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);

小开

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

小开

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

小开

例如，考虑到输入数组是按升序 asort()排序的，使用二分法搜索二分法搜索进行搜索会快得多。

下面是我用来在按 DateTime 对象排序的糟透了事件列表中插入一个新事件的一些代码的一个快速而粗糙的改编..。

因此，这段代码将返回左侧(前/小)的最近点。

如果您想找到数学上最近的点: 考虑比较搜索值与返回值的距离以及返回值右边(下一个)的点(如果存在的话)。

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

小开

我找到的基于 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

小开

二进制搜索以查找最接近的值(数组必须排序) :

function findClosest($sortedArr, $val)
{
$low = 0;
$high = count($sortedArr) - 1;
while ($low <= $high) {
if ($high - $low <= 1) {
if (abs($sortedArr[$low] - $val) < abs($sortedArr[$high] - $val)) {
return $sortedArr[$low];
} else {
return $sortedArr[$high];
}
}


$mid = (int)(($high + $low) / 2);
if ($val < $sortedArr[$mid]) {
$high = $mid;
} else {
$low = $mid;
}
}


// Empty array
return false;
}

小开

我将提供一个后期答案，通过维护两个临时变量和实现早期返回，努力避免不必要的迭代和过多的函数调用。

一个优雅的解决方案不应该需要比 N更大的时间复杂度——换句话说，大的哦应该是 O (n)，小的哦应该是 O (1)。大的哦只是通过预先分类干草堆，然后再次迭代干草堆而变得更糟。要实现 O (1)，遇到相同匹配时需要提前返回——不需要进一步搜索。

我的代码片段将任意返回具有最小距离的第一个出现的值(在多个值具有相同距离的情况下)。OP 没有指定任何其他行为。

与其他一些答案相比，一个微不足道的性能改进是，abs()是循环中唯一的函数调用，每次迭代最多调用1次。以前的一些答案会重新计算当前值的距离以及每次迭代中当前最接近的匹配项——这比必要的工作量更大。

密码: (演示)

$haystack = [-6, 0, 5, 10, 11, 12, 20];


$needles = [0, 3, 14, -3];


function getNearest($needle, $haystack) {
if (!$haystack) {
throw new Exception('empty haystack');
}
$bestDistance = PHP_INT_MAX;
foreach ($haystack as $value) {
if ($value === $needle) {
return $needle;
}
$distance = abs($value - $needle);
if ($distance < $bestDistance) {
$bestDistance = $distance;
$keep = $value;
}
}
return $keep ?? $value; // coalesce to silence potential IDE complaint
}


foreach ($needles as $needle) { // each test case
echo "$needle -> " . getNearest($needle, $haystack) . "\n";
}

产出:

0 -> 0
3 -> 5
14 -> 12
-3 -> -6

小开

这是与马里奥的回答相同的方法，但是我使用 array_search()和 min()代替排序。性能是一样的，所以归根结底就是偏好的问题。

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