JavaScriptで昇順配列の中から並び順を壊している唯一の要素を見つける方法

この記事では、昇順（増加順）にソートされた数値の配列の中に、ただひとつだけ並び順を乱している要素がある場合に、その要素を特定して返すJavaScript関数の実装方法を解説します。

問題の定義

扱う配列は基本的に昇順でソートされていますが、その中の要素がひとつだけ順序から外れています。関数の目的は、その「異常な要素」を見つけ出して返すことです。

たとえば、次のような配列を考えます。

const arr = [1, 2, 3, 4, 17, 5, 6, 7, 8];

この配列から「17」を取り除けば残りは完全な昇順になるため、求める答えは「17」です。

解決のアプローチ

昇順の配列では、隣り合う任意の2要素について常に「前の要素 ≤ 次の要素」という関係が成り立ちます。そこで、配列を先頭から1回走査しながら隣接要素を比較すれば、この関係が初めて崩れた位置に異常な要素が存在すると特定できます。

さらに、並びが崩れた箇所で「前の要素と後ろの要素のどちらを取り除けば元の昇順が復元できるか」を判定することで、左右どちら側の要素が原因でも正確に対応できます。

コード例

const arr = [1, 2, 3, 4, 17, 5, 6, 7, 8];

const findWrongNumber = (arr = []) => {
  for (let i = 0; i < arr.length - 1; i++) {
    // 昇順が崩れている箇所を検出
    if (arr[i] > arr[i + 1]) {
      // 前後の要素との大小関係から、どちらが異常な要素かを判定
      const prevFits = i === 0 || arr[i - 1] <= arr[i + 1];
      return prevFits ? arr[i] : arr[i + 1];
    }
  }
};

console.log(findWrongNumber(arr));

出力結果

17

コードの解説

• 走査： forループで配列を先頭から順にたどり、隣り合う要素 arr[i] と arr[i + 1] を比較します。
• 崩れの検出： arr[i] > arr[i + 1] となった時点で、昇順が破られていることが分かります。
• 異常要素の判定： arr[i - 1] ≤ arr[i + 1] が成立する場合は arr[i] を除けば並びが復元できるため arr[i] が異常、成立しない場合は arr[i + 1] が異常です。i === 0 の場合は先頭要素が異常とみなします。
• 計算量： 配列を1回だけ走査するため、時間計算量はO(n)、追加のメモリ使用量はO(1)と効率的です。

この手法なら、異常な要素が大きすぎるケースだけでなく、小さすぎるケース（例：[1, 2, 0, 3, 4]）にも正しく対応できます。