C++の回転ソート配列IIで最小値を見つける

並べ替えられた配列があり、それがピボットで回転しているとします。ピボットはこれまで知られていません。その配列から最小要素を見つける必要があります。したがって、配列が[4,5,5,5,6,8,2,3,4]のような場合、最小要素は2です。

これを解決するには、次の手順に従います-

• search（）と呼ばれる1つのメソッドを定義します。これには、arr、low、highが必要です

• low =highの場合、arr [low]

  を返します

• 中：=低+（高–低）/ 2

• ans：=inf

• arr [low]

• それ以外の場合、arr [high]> arr [mid]の場合、ans：=arr [mid]の分とsearch（arr、low、mid）

• それ以外の場合、arr [low] =arr [mid]の場合、ans：=arr [low]の最小値とsearch（arr、low + 1、high）

• それ以外の場合、arr [high] =arr [mid]の場合、ans：=arr [high]の最小値とsearch（arr、low、high-1）

• ansを返す

• メインメソッドの呼び出しからsolve（nums、0、size of nums – 1）

例

理解を深めるために、次の実装を見てみましょう-

#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