Comment implémenter l'algorithme de recherche du nombre avec la plus petite valeur absolue dans un tableau ordonné en PHP

Cet article présente principalement l'algorithme PHP pour trouver le nombre avec la plus petite valeur absolue dans un tableau ordonné, et analyse brièvement les compétences opérationnelles associées aux algorithmes de traversée de tableau et de recherche binaire. Les amis dans le besoin peuvent s'y référer

<.> L'exemple de cet article décrit l'algorithme PHP permettant de trouver le nombre avec la plus petite valeur absolue dans un tableau ordonné. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Question :

Un tableau ordonné, la valeur peut avoir une valeur négative , ou il se peut que non, nous devons maintenant trouver la valeur avec la plus petite valeur absolue.

Méthode 1 :

Parcourez le tableau et trouvez la valeur minimale absolue. La complexité temporelle est O(n), n est le nombre d'éléments.

Méthode 2 :

Recherche binaire, car le tableau est ordonné, la recherche binaire peut être utilisée et la complexité temporelle est O(logn).

Étapes d'analyse :

1 Si le premier nombre est positif, cela signifie qu'il n'y a pas de nombre négatif dans l'ensemble du tableau, et le. le premier nombre est renvoyé directement

2. Si le dernier nombre est un nombre négatif, cela signifie qu'il n'y a pas de nombre positif dans tout le tableau, et le dernier nombre sera renvoyé directement

3. . Les éléments du tableau sont positifs ou négatifs, ce qui signifie que l'élément avec la plus petite valeur absolue doit être dans A la jonction des nombres positifs et négatifs, une recherche binaire est requise :

① Si a[mid]<. ;0, parce que le tableau est par ordre croissant, cela signifie que le nombre avec la plus petite valeur absolue n'apparaîtra pas sur le côté gauche de a[mid], et en même temps déterminera le positif ou le négatif de l'élément a[mid +1] S'il s'agit d'un nombre négatif, alors vous devez rechercher dans l'intervalle situé à droite du milieu. Si a[mid-1] n'est pas négatif, cela signifie que ces deux nombres sont l'intersection positive et négative. points dans le tableau, renvoie la plus petite valeur absolue des deux nombres.

②. Si a[mid]>0, parce que le tableau est en ordre croissant, cela signifie que le nombre avec la plus petite valeur absolue n'apparaîtra pas sur le côté droit de a[mid], et à en même temps, déterminez le positif ou le négatif de l'élément a[mid-1] , s'il s'agit d'un nombre négatif, cela signifie que les deux nombres sont les points d'intersection positifs et négatifs dans le tableau, et la valeur absolue des deux nombres est plus petit Si a[mid-1] n'est pas négatif, alors il doit être dans l'intervalle à gauche de mid.

③. Si a[mid] == 0, alors a[mid] est le plus petit élément absolu.

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;

Résultat de l'exécution : 4

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!