найти подходящее или ближайшее значение в массиве

<p>как я могу найти и найти для заданного целевого значения самое близкое значение в массиве?</p><p>допустим, у меня есть этот примерный массив:</p><pre><code>array(0, 5, 10, 11, 12, 20) </code></pre><p>например, когда я ищу с целевым значением 0, функция должна вернуть 0; когда я ищу с 3, он возвращает 5; когда я ищу с 14, он вернется 12.</p>

<p>передайте число, которое вы ищете, в качестве первого параметра, а массив чисел - во второй:</p><pre><code>function getclosest($search, $arr) { $closest = null; foreach ($arr as $item) { if ($closest === null || abs($search - $closest) > abs($item - $search)) { $closest = $item; } } return $closest; } 

это высокопроизводительная функция, для которой я написал<strong> отсортировал большие массивы </strong>протестировано, основной цикл требует всего ~ 20 итераций для массива с 20000 элементами. <strong> пожалуйста, обратите внимание, массив должен быть отсортирован (по возрастанию)! </strong>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]; } </code></pre><ul> <li><code>array\_nearest\_default</code> находит ближайший элемент</li> <li><code>array\_nearest\_lower</code> находит ближайший элемент, который является ниже</li> <li><code>array\_nearest\_higher</code> находит ближайший элемент, который является более высоким</li> </ul><p><strong> использование: </strong></p><pre><code>$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); </code></pre>

<p>особый ленивый подход заключается в сортировке php массива по расстоянию до искомого числа:</p><pre><code>$num = 3; $array = array(0, 5, 10, 11, 12, 20); foreach ($array as $i) { $smallest[$i] = abs($i - $num); } asort($smallest); print key($smallest); </code></pre>

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

<p>вы можете просто использовать <code>array\_search</code> для этого, он возвращает один единственный ключ, если в массиве будет найдено много экземпляров поиска, он вернет первый найденный им ключ.</p><p> <a href="http://php.net/manual/en/function.array-search.php">цитата из php</a> :</p><blockquote> <p>если игла найдена в стоге сена более одного раза, возвращается первый соответствующий ключ. чтобы вернуть ключи для всех совпадающих значений, используйте <a href="http://www.php.net/manual/en/function.array-keys.php">array\_keys ()</a> с необязательным параметром search\_value.</p> </blockquote><p>пример использования:</p><pre><code>if(false !== ($index = array_search(12,array(0, 5, 10, 11, 12, 20)))) { echo $index; //5 } </code></pre><hr><p>обновление:</p><pre><code>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; } </code></pre>

<p>для поиска ближайшего значения в массиве объектов вы можете использовать этот адаптированный код из <a href="https://stackoverflow.com/a/5464961/496176">ответа тима купера</a> .</p><pre><code><?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); ?> </code></pre>

<p> <a href="https://stackoverflow.com/a/5464961/368691">реализация тима</a> будет сокращать его большую часть времени. тем не менее, для повышения производительности вы можете отсортировать список до итерации и прервать поиск, когда следующая разница больше последней.</p><pre><code><?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] ); } 

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; } это должно дать вам то, что вам нужно.

учитывая, что входной массив отсортирован в порядке возрастания, например, asort(), вы будете выполнять поиск намного быстрее, используя <a href="https://en.wikipedia.org/wiki/dichotomic_search">дихотомический поиск . вот быстрая и грязная адаптация некоторого кода, который я использую для вставки нового события в <a href="http://php.net/manual/en/class.iterator.php">iterable список событий, отсортированный по объектам 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); } </code></pre>