सी ++ में घुमाए गए क्रमबद्ध सरणी में न्यूनतम खोजें

मान लीजिए कि एक सरणी है, और इसे क्रमबद्ध किया गया है, मान लें कि सरणी को किसी धुरी पर घुमाया गया है, जो हमारे लिए अज्ञात है। तो हमें उस घुमाए गए सरणी से न्यूनतम खोजना होगा। तो अगर ऐरे [3,4,5,1,2] जैसा है, तो आउटपुट 1 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• निम्न:=0 और उच्च:=सरणी की अंतिम अनुक्रमणिका, n:=सरणी का आकार, उत्तर:=अनंत
• जबकि कम <=उच्च
  • मध्य :=निम्न + (उच्च-निम्न)/2
  • अगर गिरफ्तारी [कम] <एआर [मध्य], तो उत्तर:=न्यूनतम उत्तर और एआर [कम], निम्न:=मध्य + 1
  • अन्यथा अगर एआर [उच्च]> एआर [मध्य], तो उत्तर:=न्यूनतम उत्तर और एआर [मध्य], उच्च:=मध्य – 1
  • अन्यथा यदि निम्न =मध्य, तो उत्तर :=न्यूनतम उत्तर और आगमन [निम्न], निम्न :=मध्य + 1
  • अन्यथा यदि उच्च =मध्य, तो उत्तर:=न्यूनतम उत्तर और एआर [उच्च], उच्च:=मध्य - 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