Find a matching or closest value in an array
PhpArraysSearchSortingPhp Problem Overview
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.
Php Solutions
Solution 1 - Php
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;
}
Solution 2 - Php
A particular lazy approach is having PHP sort the array by the distance to the searched number:
$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);
Solution 3 - Php
This is high-performance function I wrote for sorted big arrays
Tested, main loop needs only ~20 iterations for an array with 20000 elements.
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 elementARRAY_NEAREST_LOWERfinds nearest element which is LOWERARRAY_NEAREST_HIGHERfinds nearest element which is 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);
Solution 4 - Php
<?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);
}
?>
Solution 5 - Php
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] );
}
Solution 6 - Php
To search the nearest value into an array of objects you can use this adapted code from 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);
?>
Solution 7 - Php
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;
}
Solution 8 - Php
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.
> 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.
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;
}
Solution 9 - Php
Considering that the input array is sorted in ascending order asort() for example, you'll be far faster to search using a dichotomic search.
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…
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);
}
Solution 10 - Php
Best method I've found based on Piyush Dholariya's answer:
$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
Solution 11 - Php
Binary search to find closest value (array must be sorted):
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;
}
Solution 12 - Php
I'll provide a late answer that endeavors to avoid needless iterations and excessive function calls by maintaining two temporary variables and implementing an early return.
An elegant solution should not require a time complexity greater than n -- in other words, the big O should be O(n) and the little o should be o(1). The big O only gets worse by pre-sorting the haystack, then iterating the haystack again. To get achieve o(1), you will need an early return when an identical match is encountered -- there is no need to search further.
My snippet will arbitrarily return the first occurring value with the lowest distance (in case multiple values have the same distance). Any other behavior is not specified by the OP.
A trivial performance improvement over some other answers is that abs() is the lone function call within the loop and it is called a maximum of 1 time per iteration. Some previous answers recalculate the distance of the current value as well as the current closest match on each iteration -- this is more work than is necessary.
Code: (Demo)
$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";
}
Output:
0 -> 0
3 -> 5
14 -> 12
-3 -> -6
Solution 13 - Php
This is the same approach as Mario's answer, but I use array_search() and min() instead of sorting. The performance is the same, so it just comes down to the matter of preference.
function findClosest(array $values, $match)
{
$map = [];
foreach ($values as $v) {
$map[$v] = abs($match - $v);
}
return array_search(min($map), $map);
}