JavaScriptでソートされていない配列から最大値と最小値を線形時間で求める方法

はじめに

JavaScriptでは、ソートされていない数値の配列から最大値と最小値を効率的に取り出したいケースがよくあります。本記事では、線形時間（O(n)）かつ定数領域（O(1)）で動作する関数を実装し、最小値（min）と最大値（max）を含むオブジェクトとして返す方法を解説します。

実装の考え方

アプローチは非常にシンプルです。まず配列の先頭要素を最大値・最小値の初期値として設定し、その後、配列全体を一度だけ走査します。走査中に現在の最大値より大きい要素が見つかれば最大値を更新し、現在の最小値より小さい要素が見つかれば最小値を更新していきます。これにより、配列をソートすることなく1回のループで両方の値を取得できます。

コード例

以下は実際のコードです。

const arr = [112, 24, 31, 44, 101, 203, 33, 56];
const findMaxMin = (arr) => {
    let max = arr[0];
    let min = arr[0];
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
        else if (arr[i] < min) {
            min = arr[i];
        }
    };
    return {
        min, max
    };
};
console.log(findMaxMin(arr));

出力結果

コンソールには以下のように表示されます。

{ min: 24, max: 203 }

パフォーマンスについて

このアルゴリズムは配列を1回だけ走査するため、時間計算量はO(n)であり、追加のメモリも不要なので空間計算量はO(1)です。大規模な配列でも高速に動作します。また、if / else if の構造を採用しているため、各要素との比較回数も抑えられ、無駄のない処理になっています。