Trouver une valeur correspondante ou la plus proche dans un tableau

Question

Comment puis-je chercher et trouver, pour une valeur cible donnée, la valeur la plus proche dans un tableau ?

Disons que j'ai ce tableau exemplaire :

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

Par exemple, lorsque je cherche avec la valeur cible 0, la fonction renvoie 0 ; lorsque je cherche avec 3, elle renvoie 5 ; lorsque je cherche avec 14, elle renvoie 12.

Answer 1

Essayez ceci cela ne donne pas seulement la correspondance la plus proche mais fournit à la fois la valeur supérieure et la valeur inférieure la plus proche d'un nombre donné.

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

Answer 2

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

Answer 3

J'ai converti la réponse acceptée en Kotlin avec quelques modifications. N'hésitez pas à les modifier en fonction de vos besoins.

private fun getClosestTo1(array: List<Float>): Float? {
            var closest: Float? = null
            for (item in array) {
                if (item == 1.0f) {
                    return item
                } else if (closest == null || abs(1.minus(closest)) > abs(item - 1)) {
                    closest = item
                }
            }

            return closest
        }

Answer 4

Recherche binaire pour trouver la valeur la plus proche (le tableau doit être trié) :

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 5

Je vais fournir une réponse tardive qui s'efforce d'éviter les itérations inutiles et les appels de fonction excessifs en maintenant deux variables temporaires et en mettant en place un retour anticipé.

Une solution élégante ne devrait pas exiger une complexité temporelle supérieure à n -- en d'autres termes, le grand O devrait être O(n) et le petit o devrait être o(1) . Le grand O ne fait qu'empirer en pré-triant la meule de foin, puis en itérant à nouveau la meule de foin. Pour arriver à o(1) vous aurez besoin d'un retour rapide lorsqu'une correspondance identique est rencontrée - il n'est pas nécessaire de chercher plus loin.

Mon extrait renvoie arbitrairement la première valeur apparaissant avec la distance la plus faible (dans le cas où plusieurs valeurs ont la même distance). Tout autre comportement n'est pas spécifié par l'OP.

Une amélioration triviale des performances par rapport à d'autres réponses est que abs() est le seul appel de fonction dans la boucle et il est appelé au maximum une fois par itération. Certaines réponses précédentes recalculent la distance de la valeur actuelle ainsi que la correspondance la plus proche à chaque itération - c'est plus de travail que nécessaire.

Code : ( Démo )

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

Sortie :

0 -> 0
3 -> 5
14 -> 12
-3 -> -6