C++ में घूर्णी क्रमबद्ध सरणी II में न्यूनतम ढूंढें

मान लीजिए हमारे पास एक सरणी है जो क्रमबद्ध है, अब वह कुछ पिवट पर घूमी हुई है। पिवट पहले से ज्ञात नहीं है। हमें उस सरणी से न्यूनतम तत्व ढूंढना है। तो यदि सरणी [4,5,5,5,6,8,2,3,4] जैसी है, तो न्यूनतम तत्व 2 है।

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

• एक विधि search() परिभाषित करें, जो arr, low और high लेती है

• यदि low = high, तो arr[low] लौटाएं

• mid := low + (high - low) / 2

• ans := inf

• यदि arr[low] < arr[mid], तो ans := arr[low] और search(arr, mid, high) का न्यूनतम

• अन्यथा जब 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, 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