C++ में घुमाए गए सॉर्ट किए गए ऐरे II में न्यूनतम खोजें

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

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

• खोज () नामक एक विधि को परिभाषित करें, इसमें गिरफ्तारी, निम्न और उच्च की आवश्यकता होती है

• यदि निम्न =उच्च है, तो वापसी आगमन [निम्न]

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

• Ans :=inf

• अगर arr[low]

• अन्यथा जब arr[high]> arr[mid], तब ans :=min of arr[mid] और search(arr, low, mid)

• अन्यथा जब arr[low] =arr[mid], तब ans :=min of arr[low] और search(arr, low + 1, high)

• अन्यथा जब arr[high] =arr[mid], तब ans :=min of arr[high] और search(arr, low, high - 1)

• वापसी उत्तर

• मुख्य विधि से कॉल हल करें(अंक, 0, अंकों का आकार -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