C++でソート済み・回転配列から最大要素を効率的に求める方法

問題の概要

昇順にソートされた重複のない要素を持つ配列が、ある未知の位置で回転されているとします。この記事では、二分探索の考え方を活用し、O(log n) の計算量で配列内の最大要素を効率的に見つける C++ プログラムを紹介します。

例

たとえば、入力配列が {30, 40, 50, 10, 20} の場合、最大要素は 50 になります。

アルゴリズム

回転されたソート済み配列には、次のような重要な性質があります。最大要素は「隣接する次の要素が自分より小さい」という条件を満たす唯一の要素です。もし次の要素が自分より小さい要素が存在しなければ、配列は回転されていないことになり、最後の要素が最大となります。

具体的な手順は以下のとおりです。

• 中央の要素(mid)について、mid − 1 と mid + 1 の位置にある要素と比較することで、上記の条件を満たしているかどうかを確認します。
• 最大要素が中央付近に存在しない場合(mid でも mid + 1 の位置でもない)、最大要素は左半分または右半分のどちらかにあります。
  • 中央の要素が配列の末尾の要素より大きい場合、最大要素は左半分にあります。
  • それ以外の場合、最大要素は右半分にあります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// ソート済み・回転配列から最大要素を再帰的に求める関数
int getMaxInSortedAndRotated(int arr[], int low, int high) {
    // 探索範囲が無効な場合は先頭の要素を返す(回転なし)
    if (high < low) {
        return arr[0];
    }
    // 探索範囲が1要素のみの場合
    if (high == low) {
        return arr[high];
    }
    int mid = low + (high - low) / 2;
    // 中央の要素が最大であるかどうかを判定
    if (mid < high && arr[mid + 1] < arr[mid]) {
        return arr[mid];
    }
    // 直前の要素が最大であるかどうかを判定
    if (mid > low && arr[mid] < arr[mid - 1]) {
        return arr[mid - 1];
    }
    // 最大要素がある側の半分を再帰的に探索
    if (arr[low] > arr[mid]) {
        return getMaxInSortedAndRotated(arr, low, mid - 1);
    } else {
        return getMaxInSortedAndRotated(arr, mid + 1, high);
    }
}

int main() {
    int arr[] = {30, 40, 50, 10, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum element = " << getMaxInSortedAndRotated(arr, 0, n - 1) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum element = 50

まとめ

このアルゴリズムは二分探索を応用しているため、すべての要素を順番に調べる線形探索の O(n) に対して、O(log n) という計算量で最大要素を求められます。要素数が多い配列でも高速に動作するのが大きなメリットです。