C++で重複を含む回転ソート配列の最小値を見つける方法

ソート済みの配列が、ある未知のピボット位置を基準に回転されているとします。このとき、配列の中から最小の要素を見つける必要があります。例えば、配列が [4,5,5,5,6,8,2,3,4] のような場合、最小要素は 2 となります。

この問題は「回転ソート配列I」と似ていますが、配列に重複した値が含まれる点が異なります。重複があると単純な二分探索では判断が難しくなるため、条件分岐を工夫して探索範囲を狭めていく必要があります。

アルゴリズムの考え方

以下の手順で問題を解きます。

• search() というメソッドを定義する。引数は配列 arr、探索範囲の下限 low、上限 high。
• low == high の場合、それ以上分割できないので arr[low] を返す。
• mid := low + (high – low) / 2 として中央位置を計算する。
• ans := INT_MAX（無限大）で初期化する。
• arr[low] < arr[mid] の場合：左半分はソート済みなので、ans := min(arr[low], search(arr, mid, high))。
• arr[high] > arr[mid] の場合：右半分はソート済みなので、ans := min(arr[mid], search(arr, low, mid))。
• arr[low] == arr[mid] の場合：どちらが最小か判断できないため、左端を1つずらして ans := min(arr[low], search(arr, low + 1, high))。
• arr[high] == arr[mid] の場合：同様に右端を1つずらして ans := min(arr[high], search(arr, low, high - 1))。
• 最後に ans を返す。

メイン処理からは solve(nums, 0, 配列サイズ – 1) を呼び出して探索を開始します。

計算量について

重複がない場合は O(log n) で解けますが、重複が含まれる場合、最悪ケース（すべて同じ値など）では範囲を1つずつ縮めるため O(n) になります。これは重複ありの回転配列における理論上の下限でもあります。

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 = INT_MAX;
        if(arr[low] < arr[mid]){
            ans = min(arr[low], search(arr, mid, high));
        }
        else if (arr[high] > arr[mid]){
            ans = min(arr[mid], search(arr, low, mid));
        }
        else if(arr[low] == arr[mid]){
            ans = min(arr[low], search(arr, low + 1, high));
        }
        else if(arr[high] == arr[mid]){
            ans = min(arr[high], search(arr, low, high - 1));
        }
        return ans;
    }
    int findMin(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.findMin(v));
}

入力

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

出力

2

まとめ

重複を含む回転ソート配列の最小値を求めるには、二分探索をベースにしつつ、arr[low] や arr[high] が arr[mid] と等しい場合に探索範囲を少しずつ狭める工夫が必要です。これにより、重複による曖昧さを回避しながら正確に最小値を特定できます。