如何在数组中搜索并找到最接近给定目标值的值?
假设我有以下示例数组:
array(0, 5, 10, 11, 12, 20)
例如,当我使用目标值0进行搜索时,该函数应返回0;当我使用3进行搜索时,它应返回5;当我使用14进行搜索时,它应返回12。你可以简单地使用array_search
来实现,它会返回一个单一的键,如果在数组中找到了多个搜索实例,则会返回它找到的第一个。
如果needle在haystack中出现多次,则返回第一个匹配的键。要返回所有匹配值的键,请改用带有可选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;
}
我将提供一个晚一些的答案,它通过维护两个临时变量并实现早期返回来避免不必要的迭代和过多的函数调用。
优雅的解决方案不应该需要大于n的时间复杂度--换句话说,大O应该是O(n),小o应该是o(1)。如果预先对干草堆进行排序,然后再迭代干草堆,大O只会变得更糟。为了实现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
二分查找以找到最接近的值(数组必须排序):
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;
}