सी ++ में घुमाई गई सूची में अधिकतम संख्या खोजने का कार्यक्रम

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

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

• निम्न:=0 और उच्च:=सरणी का अंतिम सूचकांक, n:=सरणी का आकार, उत्तर:=0

• जबकि कम <=उच्च

  • मध्य :=निम्न + (उच्च-निम्न)/2

  • अगर गिरफ्तारी [कम] <एआर [मध्य], तो उत्तर:=अधिकतम उत्तर और एआर [कम], कम:=मध्य + 1

  • और अगर arr[high]> arr[mid], तो ans :=अधिकतम ans और arr[mid], high :=mid – 1

  • अन्यथा यदि निम्न =मध्य, तो उत्तर:=अधिकतम उत्तर और आगमन [निम्न], निम्न:=मध्य + 1

  • और अगर उच्च =मध्य, तो उत्तर:=अधिकतम उत्तर और गिरफ्तारी [उच्च], उच्च:=मध्य - 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 = 0;
      if(arr[low] < arr[mid]){
         ans = max(arr[low], search(arr, mid, high));
      }
      else if (arr[high] > arr[mid]){
         ans = max(arr[mid], search(arr, low, mid));
      }
      else if(arr[low] == arr[mid]){
         ans = max(arr[low], search(arr, low + 1, high));
      }
      else if(arr[high] == arr[mid]){
         ans = max(arr[high], search(arr, low, high - 1));
      }
      return ans;
   }
   int findMax(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.findMax(v));
}

इनपुट

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

आउटपुट

8