C++で配列内の局所最小値（極小値）を二分探索で見つける方法

n個の要素を持つ配列Aを考えます。この配列の中から局所最小値（極小値）を見つける必要があります。

配列Aにおいて、要素A[x]は、その両隣の要素のどちらとも比較して自分以下である場合に「局所最小値」と呼ばれます。ただし、配列の端にある要素については隣接要素が1つしか存在しないため、その1つとのみ比較を行います。また、局所最小値が複数存在する場合は、そのうちのどれか1つを返せばよいものとします。

例えば、配列が [9, 6, 3, 14, 5, 7, 4] の場合を考えてみましょう。このとき局所最小値となるのは 3、5、4 の3つであり、本アルゴリズムはこれらのうちの1つを返します。

解法のアプローチ：二分探索の活用

この問題を効率的に解くには、二分探索と同様のロジックを応用します。手順は以下の通りです。

• 配列の中央要素が左右両方の隣接要素より小さい場合、そのインデックス mid を返す。
• 中央要素が左隣の要素より大きい場合、左側半分に局所最小値が存在する可能性があるため、左側を再帰的に探索する。
• 中央要素が右隣の要素より大きい場合、右側半分に局所最小値が存在する可能性があるため、右側を再帰的に探索する。

この手法により、線形探索ではO(n)かかるところを、O(log n) の計算量で局所最小値を発見できます。

サンプルコード

#include<iostream>
using namespace std;
int localMinima(int arr[], int left, int right, int n) {
    int mid = left + (right - left)/2;
    if ((mid == 0 || arr[mid-1] > arr[mid]) && (mid == n-1 || arr[mid+1] > arr[mid]))
        return mid;
    else if (mid > 0 && arr[mid-1] < arr[mid])
        return localMinima(arr, left, (mid -1), n);
    return localMinima(arr, (mid + 1), right, n);
}
int findLocalMinima(int arr[], int n) {
    return localMinima(arr, 0, n-1, n);
}
int main() {
    int arr[] = {9, 6, 3, 14, 5, 7, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
}

実行結果

Local minima is: 3

このプログラムでは、配列 {9, 6, 3, 14, 5, 7, 4} から局所最小値として 3 が出力されます。境界条件（配列の先頭・末尾）も適切に判定しているため、どんな入力配列に対しても正しく動作します。