배열에서 일치하거나 가장 가까운 값 찾기

배열에서 일치하거나 가장 가까운 값 찾기

---

주어진 대상 값에 대해 배열에서 가장 가까운 값을 검색하고 찾으려면 어떻게해야합니까?

이 예제 배열이 있다고 가정 해 보겠습니다.

array(0, 5, 10, 11, 12, 20)

예를 들어, 목표 값 0으로 검색하면 함수는 0을 반환합니다. 3으로 검색하면 5가 반환됩니다. 14로 검색하면 12를 반환합니다.

---

검색중인 숫자를 첫 번째 매개 변수로 전달하고 숫자 배열을 두 번째 매개 변수로 전달하십시오.

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

---

특정 게으른 접근 방식은 PHP가 검색된 숫자까지의 거리에 따라 배열을 정렬하도록하는 것입니다.

$num = 3;    
$array = array(0, 5, 10, 11, 12, 20);

foreach ($array as $i) {
    $smallest[$i] = abs($i - $num);
}
asort($smallest);
print key($smallest);

---

이것은 정렬 된 큰 배열을 위해 작성한 고성능 함수입니다.

테스트 된 메인 루프는 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 가장 가까운 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);

---

<?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에서 인용 :

바늘이 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;
}

---

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

---

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()예를 들어 입력 배열이 오름차순으로 정렬된다는 점을 고려 하면 dichotomic search를 사용하여 검색하는 것이 훨씬 빠릅니다 .

다음 은 DateTime 개체별로 정렬 된 Iterable 이벤트 목록 에 새 이벤트를 삽입하는 데 사용하는 일부 코드의 빠르고 더러운 수정입니다 .

따라서이 코드는 왼쪽에서 가장 가까운 지점 (전 / 작은)을 반환합니다.

수학적으로 가장 가까운 지점을 찾으려면 검색 값의 거리를 반환 값 및 반환 값 (존재하는 경우) 바로 오른쪽 (다음)에있는 지점과 비교해보십시오.

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

---

시도해보십시오. 이것은 가장 가까운 일치를 제공 할뿐만 아니라 주어진 숫자보다 가장 가까운 높은 값과 가장 가까운 낮은 값을 모두 제공합니다.

 getNearestValue(lookup_array, lookup_value) {

        if (lookup_array.length > 0) {
          let nearestHighValue = lookup_array[0];
          let nearestLowValue = lookup_array[0];
          let nearestValue=0;
          let diff, diffPositive = Infinity;
          let diffNeg = -Infinity;
          lookup_array.forEach(num => {
            diff = lookup_value - num;
            if (diff >= 0 && diff <= diffPositive) {
              nearestLowValue = num;
              diffPositive = diff;
            }
            if (diff <= 0 && diff >= diffNeg) {
              nearestHighValue = num;
              diffNeg = diff;
            }

          })
          //If no value is higher than GivenNumber then  keep nearest low value as clossets
          if (diffNeg == -Infinity) {
            nearestHighValue = nearestLowValue;
          }
              //If no value is Lower than Givennumber then  keep nearest High value as clossets
          if (diffPositive == Infinity) {
            nearestLowValue = nearestHighValue;
          }
          if((lookup_value-nearestLowValue)<=(nearestHighValue-lookup_value))
            {
              nearestValue=nearestLowValue;
             }
         else
            {
            nearestValue=nearestHighValue;
            }
          return { NearHighest: nearestHighValue, NearLowest: nearestLowValue,NearestValue:nearestValue };
        }
        else {
          return null;
        }
      }

---

    $closest = 0;
    while ($rowDecontos = mysql_fetch_array($pvDescontos)) {
        if ($rowDecontos['n_dias'] > $closest && $rowDecontos['n_dias'] <= $numDias) {
            $closest = $rowDecontos['n_dias'] ;
        }
    };

---

try this: (it has not been tested)

function searchArray($needle, $haystack){
    $return = $haystack[0];
    $prevReturn = $return;
    foreach($haystack as $key=>$val){
         if($needle > $val) {
            $prevReturn = $return;
            $return = $val;
         }
         if($val >= $needle) {
            $prevReturn = $return;
            $return = $val;
            break;
         }
    }
    if((($return+$needle)/2) > (($prevReturn+$needle)/2)){
         //means that the needle is closer to $prevReturn
         return $prevReturn;
    }
    else return $return;
}

---

Given code can be used to get your solution:

var counts = [4, 9, 15, 6, 2],
  goal = 5;

var closest = counts.reduce(function(prev, curr) {
  return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});

console.log(closest);

ReferenceURL : https://stackoverflow.com/questions/5464919/find-a-matching-or-closest-value-in-an-array