C++で回転されたソート済み配列から最大値を見つける方法

問題概要

昇順にソートされた配列が、私たちには未知のあるピボット位置で回転されていると仮定します。この回転配列の中から最大値を見つける必要があります。例えば、配列が [3,4,5,1,2] の場合、出力は 5 となります。

解法のアプローチ

この問題は二分探索（バイナリサーチ）を応用することで効率的に解けます。先頭から順に調べる線形探索では O(n) の計算量が必要ですが、二分探索を活用すれば O(log n) まで計算量を抑えることができます。

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

• low := 0、high := 配列の最後のインデックス、n := 配列のサイズ、ans := 0 として初期化する

• low <= high の間、次の処理を繰り返す

  • mid := low + (high - low) / 2 を計算する

  • arr[low] < arr[mid] の場合：ans := ans と arr[low] の大きい方とし、low := mid + 1 とする

  • arr[high] > arr[mid] の場合：ans := ans と arr[mid] の大きい方とし、high := mid - 1 とする

  • low = mid の場合：ans := ans と arr[low] の大きい方とし、low := mid + 1 とする

  • high = mid の場合：ans := ans と arr[high] の大きい方とし、high := mid - 1 とする

• 最後に ans を返す

ここで重要なのは、回転によって配列が「昇順部分」と「昇順部分」に分割されているという性質です。中央の値と端の値を比較することで、最大値がどちら側の区間に存在するかを判定し、探索範囲を半分ずつ絞り込んでいきます。また、重複した要素が含まれるケースにも対応できるよう、low や high が mid と一致した場合の処理を設けています。

C++での実装例

以下のコードでは、再帰的な二分探索を用いて回転配列内の最大値を求めています。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int search(vector <int>& arr, int low, int high){
      if(low == high){
         return arr[low];
      }
      int mid = low + (high - low) / 2;
      int ans = 0;
      if(arr[low] < arr[mid]){
         ans = max(arr[low], search(arr, mid, high));
      }
      else if (arr[high] > arr[mid]){
         ans = max(arr[mid], search(arr, low, mid));
      }
      else if(arr[low] == arr[mid]){
         ans = max(arr[low], search(arr, low + 1, high));
      }
      else if(arr[high] == arr[mid]){
         ans = max(arr[high], search(arr, low, high - 1));
      }
      return ans;
   }
   int findMax(vector<int>& nums) {
      return search(nums, 0, nums.size() - 1);
   }
};
main(){
   Solution ob;
   vector<int> v = {4,5,5,5,6,8,2,3,4};
   cout <<(ob.findMax(v));
}

入力

[4,5,5,5,6,8,2,3,4]

出力

8

この入力例では、配列 [4,5,5,5,6,8,2,3,4] はピボット位置 8 の直後で回転されています。二分探索によって探索範囲を絞り込みながら処理を進めることで、最大値である 8 が正しく取得できています。