JavaScriptでソート済み配列に数値を挿入する方法｜二分探索で順序を維持

問題の概要

本記事では、昇順に並べ替えられた数値配列を第1引数に、単一の数値を第2引数として受け取るJavaScript関数を作成します。

関数に求められる要件は以下のとおりです。

• 第2引数で指定された数値を、配列内の適切な位置に挿入する
• 挿入後も要素のソート順（昇順）を崩さないこと
• 新しい配列を作成せず、元の配列を直接操作して実現すること

解決のアプローチ

挿入位置の特定には二分探索（バイナリサーチ）を使用します。先頭から順に比較する線形探索（計算量 O(n)）と比べ、二分探索なら O(log n) で効率的に位置を見つけられます。

位置が判明したら、その位置以降の要素を一つずつ後ろへシフトし、最後に push() メソッドで対象の数値を配列の末尾に追加します。要素のシフト時には、一時変数を使わない加減算によるスワップのテクニックを活用しています。

サンプルコード

const arr = [6, 7, 8, 9, 12, 14, 16, 17, 19, 20, 22];
const num = 15;

// 二分探索で挿入すべきインデックスを求める
const findIndex = (arr, val) => {
    let low = 0, high = arr.length;
    while (low < high) {
        let mid = (low + high) >>> 1;
        if (arr[mid] < val) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
};

// ソート順を維持したまま数値を挿入する
const insertAt = (arr = [], num) => {
    const position = findIndex(arr, num);
    for (let i = position; typeof arr[i] !== 'undefined'; i++) {
        // 一時変数を使わずに値を入れ替える
        num += arr[i];
        arr[i] = num - arr[i];
        num -= arr[i];
    }
    arr.push(num);
};

insertAt(arr, num);
console.log(arr);

実行結果

上記のコードを実行すると、コンソールに次の出力が表示されます。

[
    6, 7, 8, 9, 12,
    14, 15, 16, 17, 19,
    20, 22
]

数値 15 が 14 と 16 の間に正しく挿入され、配列全体が昇順に保たれていることが確認できます。

コードのポイント解説

• findIndex関数： 探索範囲の下限 low と上限 high を管理しながら範囲を半分に絞り込み、挿入位置を特定します。(low + high) >>> 1 は、符号なし右シフトによって中間インデックスを求める書き方です。
• insertAt関数： 挿入位置から配列末尾まで、既存の要素を一つずつ後ろへずらします。num += arr[i] → arr[i] = num - arr[i] → num -= arr[i] の3ステップで、第三の変数なしに値を交換できるのがポイントです。
• 最後のpush： シフトが完了すると、元の末尾の値が変数 num に残ります。これを配列の末尾に追加すれば、ソート順を維持した挿入が完成します。