Einführung in die Methode zum Ermitteln des minimalen Absolutwerts in einem geordneten Array mit PHP

Dieser Artikel stellt hauptsächlich den PHP-Algorithmus zum Finden der Zahl mit dem kleinsten Absolutwert in einem geordneten Array vor und analysiert kurz die damit verbundenen Bedienfähigkeiten von Array-Traversal- und binären Suchalgorithmen. Freunde in Not können sich darauf beziehen

Das Beispiel in diesem Artikel beschreibt den PHP-Algorithmus zum Finden der Zahl mit dem kleinsten Absolutwert in einem geordneten Array. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Frage:

Ein geordnetes Array, der Wert kann einen negativen Wert haben , oder nein, jetzt müssen wir den Wert mit dem kleinsten Absolutwert finden.

Methode 1:

Durchlaufen Sie das Array und finden Sie den absoluten Minimalwert. Die Zeitkomplexität ist O(n), n ist die Anzahl der Elemente.

Methode 2:

Binäre Suche: Da das Array geordnet ist, kann die binäre Suche verwendet werden und die zeitliche Komplexität beträgt O (logn).

Analyseschritte:

1 Wenn die erste Zahl positiv ist, bedeutet dies, dass es im gesamten Array keine negativen Zahlen gibt Die erste Zahl wird direkt zurückgegeben

2. Wenn die letzte Zahl eine negative Zahl ist, bedeutet dies, dass es im gesamten Array keine positive Zahl gibt und die letzte Zahl direkt zurückgegeben wird

3 . Wenn die Array-Elemente positiv oder negativ sind, bedeutet dies, dass das Element mit dem kleinsten Absolutwert in der Verbindung positiver und negativer Zahlen liegen muss:

①. <0, da das Array in aufsteigender Reihenfolge vorliegt, bedeutet dies, dass die Zahl mit dem kleinsten Absolutwert nicht auf der linken Seite von a[mid] erscheint und gleichzeitig das Positive oder Negative des Elements a[ bestimmt mid+1]. Wenn es sich um eine negative Zahl handelt, müssen Sie im Intervall auf der rechten Seite von mid-1 suchen. Wenn a[mid-1] nicht negativ ist, bedeutet dies, dass diese beiden Zahlen positiv und negativ sind Schnittpunkte im Array, gibt den kleineren Absolutwert der beiden Zahlen zurück.

② Wenn a[mid]>0, bedeutet dies, dass die Zahl mit dem kleinsten Absolutwert nicht auf der rechten Seite von a[mid] erscheint, da das Array in aufsteigender Reihenfolge ist Bestimmen Sie gleichzeitig das Positive oder Negative des Elements a[mid-1]. Wenn es eine negative Zahl ist, bedeutet dies, dass diese beiden Zahlen die positiven und negativen Schnittpunkte im Array und den absoluten Wert der beiden Zahlen sind ist kleiner. Wenn a[mid-1] nicht negativ ist, muss es im Intervall links von mid-1 liegen.

③ Wenn a[mid] == 0, dann ist a[mid] das absolut kleinste Element.

function selectAbsMinNum(array $arr)
{
  $start = 0;
  $len = count($arr) - 1;
  if ($arr[0] > 0) { //正数数组
    return $arr[0];
  }
  if ($arr[$len] < 0) { //负数数组
    return $arr[$len];
  }
  while ($start < $len) {
    $mid = floor(($start + $len) / 2);
    if ($arr[$mid] > 0) {
      if ($arr[$mid - 1] > 0) {
        $len = $mid - 1;
      } else {
        return min($arr[$mid], -$arr[$mid - 1]);
      }
    } elseif ($arr[$mid] < 0) {
      if ($arr[$mid + 1] < 0) {
        $start = $mid + 1;
      } else {
        return min(-$arr[$mid], $arr[$mid + 1]);
      }
    } else {
      return $arr[$mid];
    }
  }
}
$sortArr = [-5, -4, -4, -4, 5, 7, 9];
echo selectAbsMinNum($sortArr), PHP_EOL;

Laufergebnis: 4

Das obige ist der detaillierte Inhalt vonEinführung in die Methode zum Ermitteln des minimalen Absolutwerts in einem geordneten Array mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!