【C++】二分探索法で配列のピーク要素を効率的に見つける方法

本記事では、C++プログラムにおいて二分探索（バイナリサーチ）のアプローチを用いて、配列内のピーク要素（隣接する要素より大きい値を持つ要素）を一つ見つける方法を解説します。このアルゴリズムは、最初に見つかったピークを結果として返し、計算量はO(log(n))と非常に効率的です。

線形探索では最悪の場合O(n)の時間がかかりますが、二分探索を活用することで、探索範囲を半分ずつ絞り込みながら高速にピークを特定できます。

アルゴリズムの手順

開始
　　PeakElement()関数は、データ配列「arr」、開始インデックス、終了インデックスを引数として受け取る。
　　配列の対象範囲の中間インデックス（mid）を求める。
　　midが境界インデックスにあり、かつmidの値が隣接要素より大きい場合、midをピークとして返す。
　　midの値が左右どちらの隣接要素よりも大きい場合、midをピークとして返す。
　　midの右側の値がmid以上の場合、配列の後半部分を引数としてPeakElement()を再帰呼び出しする。
　　midの左側の値がmid以上の場合、配列の前半部分を引数としてPeakElement()を再帰呼び出しする。
終了

サンプルコード

#include<iostream>
using namespace std;
int PeakElement(int a[], int start, int end) {
   int i, mid;
   mid = (end+start+1)/2;
   if((a[mid] > a[mid+1] && mid == start)||(a[mid] > a[mid-1] && mid == end)) {
      return a[mid];
   } else if(a[mid] < a[mid-1] && a[mid] > a[mid+1]) {
      return a[mid];
   } else if(a[mid] <= a[mid+1]) {
      return PeakElement(a, mid+1, end);
   } else if(a[mid] <= a[mid-1]) {
      return PeakElement(a, start,mid-1);
   }
}
int main() {
   int n, i, p;
   cout<<"\nEnter the number of data element: ";
   cin>>n;
   int arr[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>arr[i];
   }
   p = PeakElement(arr, 0, n-1);
   cout<<"\nThe peak element of the given array is: "<<p;
   return 0;
}

実行結果

Enter the number of data element: 5
Enter element 1: 45
Enter element 2: 26
Enter element 3: 70
Enter element 4: 60
Enter element 5: 15
The peak element of the given array is: 70

上記の実行例では、入力された配列 {45, 26, 70, 60, 15} の中から、左右の隣接要素（26 と 60）のどちらよりも大きい 70 がピーク要素として検出されています。このように、二分探索を利用することで、大きな配列に対しても高速にピーク要素を見つけることが可能です。