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

配列があり、それがソートされていると仮定します。配列がピボットで回転していると考えてください。これは私たちにはわかりません。したがって、その回転した配列から最小値を見つける必要があります。したがって、配列が[3,4,5,1,2]のような場合、出力は1になります。

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

• low：=0およびhigh：=配列の最後のインデックス、n：=配列のサイズ、ans：=無限大
• 低い<=高い
  • 中：=低+（高-低）/ 2
  • arr [low]
  • それ以外の場合、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
• 回答を返す

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

例

#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