C++で回転ソート配列の最小値を二分探索で効率的に見つける方法

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

解決のためのアプローチ：二分探索

この問題は二分探索（バイナリサーチ）を応用することで効率的に解けます。単純な線形探索では O(n) の計算量がかかりますが、回転ソート配列では必ずどちらか片側の半分がソート済みになっているという性質を利用すると、計算量を O(log n) まで抑えられます。

アルゴリズムの手順

• low := 0、high := 配列の最後のインデックス、n := 配列のサイズ、ans := 無限大（INT_MAX） として初期化します。
• low <= high の間、以下を繰り返します。
  • mid := low + (high - low) / 2 として中央のインデックスを求めます。
  • arr[low] < arr[mid] の場合：左半分はソート済みなので、ans と arr[low] の小さい方を ans に代入し、low := mid + 1 とします。
  • arr[high] > arr[mid] の場合：右半分はソート済みなので、ans と arr[mid] の小さい方を ans に代入し、high := mid - 1 とします。
  • low == mid の場合：ans と arr[low] の小さい方を ans に代入し、low := mid + 1 とします。
  • high == mid の場合：ans と arr[high] の小さい方を ans に代入し、high := mid - 1 とします。
• 最終的に ans を返します。

それでは、以下の実装例を見て理解を深めましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int findMin(vector<int>& arr) {
        int low = 0;
        int high = arr.size() - 1;
        int n = arr.size();
        int ans = INT_MAX;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(arr[low] < arr[mid]){
                ans = min(ans, arr[low]);
                low = mid + 1;
            } else if(arr[high] > arr[mid]) {
                ans = min(ans, arr[mid]);
                high = mid - 1;
            } else if(low == mid) {
                ans = min(ans, arr[low]);
                low = mid + 1;
            } else if(high == mid) {
                ans = min(ans, arr[high]);
                high = mid - 1;
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {15,35,85,96,5,6,8,12};
    cout << ob.findMin(v);
}

入力

[15,35,85,96,5,6,8,12]

出力

5

計算量について

このアルゴリズムの時間計算量は O(log n) です。各反復処理で探索範囲が半分に絞られていくため、配列のサイズが大きくなっても高速に動作します。空間計算量は追加のデータ構造を使用しないため O(1) です。