PHPで順序付けられた配列内で絶対値が最小の数値を見つけるアルゴリズムを実装する方法

この記事では主に、順序付けられた配列で絶対値が最小の数値を見つけるためのアルゴリズムの PHP 実装を紹介し、配列トラバーサルと二分探索アルゴリズムの関連操作テクニックを簡単に分析します。必要な友人は参考にしてください。この記事では、PHP 実装を例とともに説明しています。 順序付けられた配列内で絶対値が最小の数値を見つけます。参考までに皆さんと共有してください。詳細は次のとおりです:

質問: 順序付けされた配列、値は負の値を持っている場合もあれば、負の値を持っていない場合もあります。今度は、絶対値が最小の値を見つける必要があります。 。

方法 1:

配列を走査し、最小の絶対値を見つけます。時間計算量は O(n)、n は要素の数です。

方法 2:

二分探索。配列は順序付けされているため、二分探索を使用でき、時間計算量は O(logn) です。

分析手順: 1. 最初の数値が正の場合、配列全体に負の数値が存在しないことを意味し、最初の数値が直接返されます

2. 最後の数値が負の場合。 、これは、配列番号全体に正の数値が存在しないことを意味し、最後の数値

3 を直接返します。負の数、二分探索が必要:

① a[mid]

②. a[mid]>0の場合、配列は昇順なので、a[mid]の右側には絶対値が最も小さい数字が現れないことを意味します。 a[mid-1] の要素が正か負か。負の数値の場合、これら 2 つの数値は配列内の正と負の交点であり、2 つの数値の絶対値の小さい方であることを意味します。 a[mid-1] が負でない場合は、mid の左側の間隔で検索する必要があります。

③. a[mid] == 0の場合、a[mid]は絶対最小の要素です。

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;

実行結果: 4

以上がPHPで順序付けられた配列内で絶対値が最小の数値を見つけるアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。