C++で最初に増加し、その後減少する配列の最大要素を二分探索で見つける方法

最初に増加し、その後減少していく配列(ビトニック配列と呼ばれます)から最大値を見つける方法を解説します。例えば、配列の要素が A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] の場合、最大値は 450 となります。

この問題は線形探索でも解けますが、二分探索(バイナリサーチ)を活用すれば、O(log n) という高速な計算量で最大値を効率的に求めることができます。

二分探索による解法のポイント

二分探索では、中央の要素(mid)とその隣接要素との大小関係に注目し、以下の3つの条件で場合分けを行います。

• mid が両隣の要素よりも大きい場合 → mid が最大値
• mid が次の要素より大きく、前の要素より小さい場合 → 最大値は mid の左側に存在する
• mid が次の要素より小さく、前の要素より大きい場合 → 最大値は mid の右側に存在する

C++での実装例

#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
    if (left == right)
        return array[left];
    if ((right == left + 1) && array[left] >= array[right])
        return array[left];
    if ((right == left + 1) && array[left] < array[right])
        return array[right];
    int mid = (left + right)/2;
    if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
        return array[mid];
    if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
        return getMaxElement(array, left, mid-1);
    else
        return getMaxElement(array, mid + 1, right);
}
int main() {
    int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
    int n = sizeof(array)/sizeof(array[0]);
    cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
}

実行結果

The maximum element is: 450

まとめ

このアルゴリズムは、配列が「増加 → 減少」という形状(ビトニック配列)であることを前提としています。再帰的に探索範囲を半分に絞り込んでいくため、要素数が多い配列でも非常に効率的に最大値を見つけられるのが特徴です。