Find a matching or closest value in an array

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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_DEFAULT finds nearest element
• ARRAY_NEAREST_LOWER finds nearest element which is LOWER
• ARRAY_NEAREST_HIGHER finds 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);

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

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.

Quote from 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.

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

Answer 13

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