Bir dizinin belirli bir değeri iki değer arasında olduğunu bulmak

4 Cevap php

Ben buna benzer bir dizi (gerçek değerler muhtemelen bu yüzden öngörülebilir olmayacak) olduğunu varsayalım:

$ar[0] = 5;
$ar[1] = 10;
$ar[2] = 15;
$ar[3] = 20;

ve ben $n = 8, ne o $n $ar[0] ve $ar[1] arasına düşer bulmak için iyi bir yol olurdu var? Bu belki de farklı büyüklükte bir dizi üzerinde bir çok kez tekrar gibi Tercihan, çözelti, tüm dizi döngü önlemek.

Edit:
Yes, the array will always be sorted.

4 Cevap

For smaller arrays...

Diziniz her zaman altta küçük değerler ile sıralanır eğer, size benzer sayısından daha büyük birine aracılığıyla döngüsü alabilirsiniz kadar. Eğer o noktaya ulaştığınızda, anahtar, ya da oraya aldı yineleme sayısını kaydedin.

Eğer tüm dizi, ve dizi sıralanır döngü istemiyorsanız, size aradığınız değerini karşılaştırmak, ortasında başlaması ve sonucu dayalı dizinin ilk yarısını veya ikinci yarısını seçebilirsiniz devam etmek.

Gerçekten kolay bir görev.

<?php
$minDiff = end($array);
$takeLesser = true;
if ($inputValue > $minDiff) {
  $itemKey = key($array);
} else { 
  foreach ($array as $key => $value) {
    $diff = abs($value - $inputValue);
    if ($minDiff < $diff) {
      break;
    }
    if ($minDiff == $diff && $takeLesser) {
      continue;
    }
    $minDiff = $diff;
    $itemKey = $key;
  }
}  
$result = $array[$itemKey];

PHP çerçeve içine yerleşik bir array_search işlevi vardır, ama doğal bir ikili arama kullanmak değildir. PHP array_search giriş komplementerleri:

<?php
    function array_bsearch( $needle, $haystack, $comparator ) {
        $high = Count( $haystack ) -1;
        $low = 0;

        while ( $high >= $low ){
            $probe = Floor( ( $high + $low ) / 2 );
            $comparison = $comparator( $haystack[$probe], $needle );
            if ( $comparison < 0 ) {
                $low = $probe +1;
            } elseif ( $comparison > 0 ) {
                $high = $probe -1;
            } else {
                return $probe;
            }
        }

      // ---The loop ended without a match
      return -1;
    }
?>

etiketler