Interview Question | Find Minimum in Rotated Sorted Array | C++
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int low=0, high=n-1;
while(low<high){
if(nums[low] <= nums[high]) return nums[low];
int mid = low + (high-low)/2;
if(nums[low] > nums[mid]){
high=mid;
} else if(nums[mid] > nums[high]) {
low=mid+1;
}
}
if(nums[low] <= nums[high]) return nums[low];
return -1;
}
English :
This C++ code defines a class called `Solution` that contains a single public member function, `findMin`, which is used to find the minimum element in a rotated sorted array. This is a common problem in computer science and is often referred to as finding the minimum element in a rotated sorted array.
Here’s a step-by-step explanation of the code:
1. The `findMin` function takes a reference to a vector of integers named `nums` as its input.
2. It first calculates the number of elements in the input vector `nums` and stores it in the variable `n`.
3. Two integer variables, `low` and `high`, are initialized to 0 and `n-1`, respectively. These variables are used to maintain a search range within the vector.
4. The code enters a `while` loop, which continues as long as the `low` index is less than the `high` index. The purpose of this loop is to perform a binary search for the minimum element in the rotated sorted array.
5. Inside the loop, the code checks if the element at the `low` index is less than or equal to the element at the `high` index. If this condition is true, it means that the remaining subarray is sorted in ascending order, and the minimum element is found at the `low` index. In this case, the function returns `nums[low]` as the minimum element.
6. If the above condition is not met, the code calculates the middle index `mid` of the current search range using the formula `low + (high — low) / 2`. This is a standard way to find the middle element without causing integer overflow.
7. The code then checks two conditions:
— If `nums[low]` is greater than `nums[mid]`, it means that the minimum element must be in the left half of the current range. Therefore, it updates the `high` index to `mid`.
— If `nums[mid]` is greater than `nums[high]`, it means that the minimum element must be in the right half of the current range. Therefore, it updates the `low` index to `mid + 1`.
8. The loop continues with the new `low` and `high` values until it finds the minimum element.
9. After the loop ends, the code checks one more time if `nums[low]` is less than or equal to `nums[high]`. If this condition is true, it means that the minimum element has been found, and it returns `nums[low]`. If not, it returns -1, indicating an error (though this case is unlikely to occur in a correctly sorted rotated array).
In summary, the code efficiently finds the minimum element in a rotated sorted array using a binary search algorithm, and it returns the minimum value once it’s identified.
Hindi :
यह सी++ कोड एक `Solution` नामक क्लास को परिभाषित करता है, जिसमें एकमात्र सार्वजनिक सदस्य संवाद, `findMin`, होता है, जिसका उपयोग परिस्थित संरेखित सूची में न्यूनतम तत्व खोजने के लिए किया जाता है। यह कंप्यूटर विज्ञान में एक सामान्य समस्या है और अक्सर इसे परिस्थित संरेखित सूची में न्यूनतम तत्व खोजने के रूप में संकेत किया जाता है।
यहाँ इस कोड की कदम-से-कदम स्थिति व्याख्या दी गई है:
1. `findMin` फ़ंक्शन एक संदर्भ को एक संख्याश्रृंगी वेक्टर `nums` के रूप में लेता है, जिसे इसका इनपुट कहा जाता है।
2. पहले इस फ़ंक्शन द्वारा इनपुट वेक्टर `nums` में तत्वों की संख्या की गणना की जाती है और इसे परिमाण `n` में संग्रहित किया जाता है।
3. दो पूर्णांक चर `low` और `high` को 0 और `n-1` के रूप में प्रारंभिक रूप से आरंभ किया जाता है। इन चरों का उपयोग वेक्टर के भीतर खोज सीमा बनाए रखने के लिए किया जाता है।
4. कोड `while` लूप में प्रवेश करता है, जिसका चालन जब तक `low` सूची अनुक्रम में `high` सूची अनुक्रम से कम होता है, चलता रहता है। इस लूप का उद्देश्य परिस्थित संरेखित सूची में न्यूनतम तत्व के लिए एक द्विआधारी खोज करना है।
5. लूप के अंदर, कोड यह जांचता है कि `low` सूची अनुक्रम में `high` सूची अनुक्रम से कम है या उसके बराबर है। अगर यह शर्त सत्य होती है, तो इसका मतलब है कि शेष सबसूची आरोही क्रम में तैयार है, और न्यूनतम तत्व `low` सूची में पाया जाता है। इस मामले में, फ़ंक्शन `nums[low]` को न्यूनतम तत्व के रूप में वापस करता है।
6. यदि उपरोक्त शर्त पूरी नहीं होती है, तो कोड वर्तमान खोज सीमा के बीच के मध्य सूची `mid` की गणना करता है, जिसके लिए फ़ार्मूला `low + (high — low) / 2` का उपयोग किया जाता है। यह एक मानक तरीका है जिससे संपूर्णांक प्रवाह को नहीं बढ़ाने के साथ मध्य तत्व को खोजा जा सकता है।
7. कोड तब दो शर्तों की जांच करता है:
— अगर `nums[low]` `nums[mid]
` से अधिक है, तो इसका मतलब है कि न्यूनतम तत्व वर्तमान सीमा के बाएं हाथ की ओर होना चाहिए। इस प्रकार, वह `high` सूची अनुक्रम को `mid` करता है।
— अगर `nums[mid]` `nums[high]` से अधिक है, तो इसका मतलब है कि न्यूनतम तत्व वर्तमान सीमा के दाएं हाथ की ओर होना चाहिए। इस प्रकार, वह `low` सूची अनुक्रम को `mid + 1` करता है।
8. लूप नए `low` और `high` मूल्यों के साथ जारी रहता है जब तक न्यूनतम तत्व पाया नहीं जाता है।
9. लूप समाप्त होने के बाद, कोड एक बार फिर जांचता है कि `nums[low]` `nums[high]` से कम है या उसके बराबर है। यदि इस शर्त परिपूर्ण होती है, तो इसका मतलब है कि न्यूनतम तत्व पाया गया है, और यह `nums[low]` को न्यूनतम तत्व के रूप में वापस करता है। अगर नहीं, तो यह -1 को वापस करता है, जिससे एक त्रुटि का सूचना देता है (हालांकि इस मामले में सही रूप से सम्परिक्षिप्त किए गए संरेखित सूची में यह घटना संभावनही है)।
संक्षेप में, यह कोड संरेखित सूची में न्यूनतम तत्व को एक द्विआधारी खोज एल्गोरिथ्म का उपयोग करके दक्षतापूर्वक खोजता है, और एक बार यह पहचान जाता है, न्यूनतम मूल्य को वापस करता है।
Hinglish :
Is C++ mein likhi gayi code ek class ko define karti hai, jise `Solution` ke naam se pukara gaya hai. Is class mein ek hi public member function hai, jise `findMin` ke naam se rakha gaya hai. Is function ka kaam ek rotate hokar sorted array mein minimum element dhoondhna hai. Ye ek common computer science problem hai, jise rotate hokar sorted array mein minimum element dhoondhna kehte hain.
Neeche diye gaye kadam-kadam taur par code ki samjhayein:
1. `findMin` function ek reference leti hai, jise `nums` ke naam se pukara gaya hai. Yani, yeh function `nums` naam ki ek integer vector ko input ke roop mein leti hai.
2. Pehle yeh function input vector `nums` mein maujood elements ki sankhya ko calculate karta hai aur use `n` naam ke variable mein store karta hai.
3. Do integer variables, `low` aur `high`, ko 0 aur `n-1` ke roop mein initialize kiya jata hai. Yeh variables vector ke andar ek search range ko maintain karne ke liye istemal hote hain.
4. Code ek `while` loop mein pravesh karta hai, jo tab tak chalta hai jab tak `low` index `high` index se chota ho. Is loop ka maksad rotate hokar sorted array mein minimum element dhundhne ke liye binary search karna hai.
5. Is loop ke andar, code dekhta hai ki `low` index par maujood element `high` index par maujood element se chhota ya barabar hai ya nahi. Agar yeh shart sahi hai, to iska matlab hai ki bache hue subarray ko ascending order mein sort kiya gaya hai aur minimum element `low` index par paya gaya hai. Is case mein, function `nums[low]` ko minimum element ke roop mein lauta deta hai.
6. Agar upar di gayi shart puri nahi hoti, to code current search range ka middle index `mid` calculate karta hai, jiska formula `low + (high — low) / 2` istemal karke nikala jata hai. Yeh ek standard tareeka hai middle element ko bina integer overflow ke nikalne ka.
7. Code fir do sharton ko dekhta hai:
— Agar `nums[low]` `nums[mid]` se bada hai, to iska matlab hai ki minimum element current range ke left half mein hoga. Isliye, `high` index ko `mid` par update kiya jata hai.
— Agar `nums[mid]` `nums[high]` se bada hai, to iska matlab hai ki minimum element current range ke right half mein hoga. Isliye, `low` index ko `mid + 1` par update kiya jata hai.
8. Yeh loop naye `low` aur `high` values ke saath chalta hai jab tak minimum element mil jata hai.
9. Jab loop khatam ho jata hai, to code ek aur baar dekhta hai ki kya `nums[low]` `nums[high]` se chota ya barabar hai. Agar yeh shart sahi hai, to iska matlab hai ki minimum element mil gaya hai, aur woh `nums[low]` ko wapas deta hai. Agar nahi, to -1 ko wapas deta hai, jo ek error ko darust karta hai (haan, yeh case sahi se rotate hokar sorted array mein asliyat mein bahut kam hota hai).
Samanya roop se, yeh code binary search algorithm ka istemal karke rotate hokar sorted array mein minimum element ko dhundhne mein safalta purvak hai, aur jab woh pahchan liya jata hai, to woh minimum value ko wapas deta hai.
