JavaScriptで回転ソート配列から最小要素を二分探索で効率的に求める方法

問題の概要

整数の配列を引数として受け取るJavaScript関数を作成する必要があります。

この配列は、まず昇順にソートされ、その後任意の数だけ回転(ローテート)されたものです。私たちの関数は、この配列の中から最小の要素を見つけて返す必要があります。

ただし、重要な条件があります。それは線形時間未満(O(n)より速い)で処理を完了しなければならないという点です。この要件を満たすために、二分探索アルゴリズムを応用した手法を使用します。

例

入力配列が次の場合:

const arr = [6, 8, 12, 25, 2, 4, 5];

この配列は [2, 4, 5, 6, 8, 12, 25] を3要素分回転させたものなので、出力は 2 となります。

解決のアプローチ

回転ソート配列には「回転点(ピボット)」と呼ばれる境界が存在し、そこを境に並び順が崩れています。最小値は必ずこの回転点上にあるため、二分探索を工夫することで O(log n) の時間計算量で最小値を特定できます。

基本的な考え方は以下の通りです:

• 中央の要素を確認し、探索範囲のどちら側に最小値があるかを判定する
• 左端の値が中央の値より小さく、中央の値が右端以下なら、整列済み部分にいるので左側へ絞り込む
• 左端の値が中央の値より大きければ、回転点は左側にあるので左へ移動する
• 重複した値(左端・中央・右端がすべて同じ)の場合は、線形に範囲を縮めて無限ループを防ぐ

実装コード

以下が実際のコードです:

const arr = [6, 8, 12, 25, 2, 4, 5];
const findMin = (arr = []) => {
    let temp;
    let min = 0;
    let max = arr.length - 1;
    let currentMin = Number.POSITIVE_INFINITY;
    while (min <= max) {
        temp = (min + max) >> 1;
        currentMin = Math.min(currentMin, arr[temp]);
        if (arr[min] < arr[temp] && arr[temp] <= arr[max] || arr[min] > arr[temp]) {
            max = temp - 1;
        } else if (arr[temp] === arr[min] && arr[min] === arr[max]) {
            let guessNum = arr[temp];
            while (min <= max && arr[min] === guessNum) {
                min++;
            }
        } else {
            min = temp + 1;
        }
    }
    return currentMin;
};
console.log(findMin(arr));

コードのポイント解説

• currentMin には初期値として Number.POSITIVE_INFINITY を設定し、走査中に遭遇した最小値を常に記録します。
• (min + max) >> 1 はビットシフト演算による中央インデックスの計算で、オーバーフローを気にせず高速に中央値を求められます。
• 重複要素への対応により、LeetCodeの「Find Minimum in Rotated Sorted Array II」のような最悪ケースでも正しく動作します。

実行結果

コンソール出力は以下の通りです:

2

このように、二分探索を応用することで、回転されたソート配列から最小要素を O(log n) の時間計算量で効率的に求めることができます。配列のサイズが大きい場合でも高速に動作するため、実務においても有用なテクニックです。