C++ में घूर्णित क्रमबद्ध सरणी (Rotated Sorted Array) में न्यूनतम तत्व खोजना

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

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

• low := 0 और high := सरणी का अंतिम सूचकांक, n := सरणी का आकार, ans := अनंत (infinity)
• जब तक low ≤ high:
  • mid := low + (high - low)/2
  • यदि arr[low] < arr[mid], तो ans := min(ans, arr[low]), low := mid + 1
  • अन्यथा यदि arr[high] > arr[mid], तो ans := min(ans, arr[mid]), high := mid – 1
  • अन्यथा यदि low = mid, तो ans := min(ans, arr[low]), low := mid + 1
  • अन्यथा यदि high = mid, तो ans := min(ans, arr[high]), high := mid - 1
• ans वापस करें

आइए निम्नलिखित कार्यान्वयन को देखें:

उदाहरण

#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;
    }
};

int 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