कम से कम क्रमबद्ध एरे में खोजें


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना माइक्रोसॉफ्ट मॉर्गन स्टेनली सैमसंग स्नैपडील टाइम्स इंटरनेट
ऐरे द्विआधारी खोज विभाजन और जीत खोजना

समस्या का विवरण

“कम से कम घुमाए गए सॉर्ट किए गए सरणी में खोजें” में कहा गया है कि आपको आकार n का एक क्रमबद्ध सरणी दिया जाता है जिसे कुछ सूचकांक में घुमाया जाता है। में न्यूनतम तत्व का पता लगाएं सरणी.

उदाहरण

कम से कम क्रमबद्ध एरे में खोजें

a[ ] = {5, 1, 2, 3, 4}
1

स्पष्टीकरण: यदि हम क्रमबद्ध क्रम में सरणी की व्यवस्था करते हैं तो यह [1, 2, 3, 4, 5] होगा। तो इन सभी में से सबसे छोटी संख्या 1. है और इसीलिए आउटपुट 1 है।

a[ ] = {5, 2, 3, 4}
2

रैखिक खोज

कलन विधि

1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialize an integer variable min as the first element in the given array.
4. Traverse through the given array and check if the element at current index in array a[ ] is less than variable min, update min as current element.
5. Return the integer variable min.

हम रैखिक खोज का उपयोग कर सकते हैं या बस एक बार इनपुट सरणी को पार कर सकते हैं और एक ही ट्रैवर्सल में सबसे छोटे तत्व का पता लगा सकते हैं। हम ऐरे में सभी तत्वों को आसानी से पा लेंगे और अगर हमें कोई ऐसा नंबर मिलता है जो हमारे न्यूनतम से कम है, तो हम अपना उत्तर अपडेट करते हैं।

कोड

C ++ प्रोग्राम रोटेटेड सॉर्ट किए गए एरे में न्यूनतम खोजने के लिए

#include <bits/stdc++.h>
using namespace std;

int findMin(int a[], int n){
    int min = a[0];
    for(int i=1; i<n; i++){
        if(a[i]<min){
            min = a[i];
        }
    }
    return min;
}

int main() {
  int a[] = {5, 2, 3, 4};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<findMin(a, n);
  return 0;
}
2

जावा प्रोग्राम को घुमाए गए सरणी में न्यूनतम खोजने के लिए

class MinSearch{
    
    static int findMin(int a[], int n){
        int min = a[0];
        for(int i=1; i<n; i++){
            if(a[i]<min){
                min = a[i];
            }
        }
        return min;
    }
    
  public static void main (String[] args){
    int a[] = {5, 2, 3, 4};
      int n = a.length;
      System.out.println(findMin(a, n));
  }
}


2

जटिलता विश्लेषण

समय जटिलता

पर),  क्योंकि हम सरणी में सभी तत्वों पर ट्रेस हुए हैं, जिससे हमें एक रैखिक समय जटिलता प्राप्त करने की अनुमति मिली है।

अंतरिक्ष जटिलता

ओ (1), एल्गोरिथ्म अपने आप में निरंतर स्थान लेता है, लेकिन इनपुट सरणी के संचय के कारण एक पूरे के रूप में कार्यक्रम रैखिक स्थान लेता है।

द्विआधारी खोज

कलन विधि

1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialise the three variables beg = 0, end = n-1 and mid = beg+(end-beg)/2.
4. Check if the variable end is less than the variable beg, return a[0].
5. If the variable end is equal to the variable beg, return a[beg].
6. If the variable mid is less than the variable end and a[mid+1] is less than a[mid], return a[mid+1].
7. If mid is greater than beg and a[mid] is less than a[mid+1], return a[mid].
8. If a[end] is greater than a[mid], make a recursive call to function with parameters a, beg, mid-1.
9. Return the recursive call to function itself with the parameters a, mid+1, and end.

द्विआधारी खोज का उपयोग करने के लिए अधिक कुशल दृष्टिकोण होगा क्योंकि इनपुट सरणी एक घुमा हुआ क्रमबद्ध सरणी है। यह सरणी क्रमबद्ध है, लेकिन इसे एक बिंदु पर घुमाया गया था। चूंकि बाइनरी खोज लॉगरिदमिक समय जटिलता लेता है। ऊपर दिए गए की तुलना में इस समाधान का उपयोग करना बेहतर है।

बाइनरी खोज का उपयोग करके घुमाए गए सॉर्ट किए गए सरणी में न्यूनतम खोजने के लिए कोड

C ++ प्रोग्राम

#include <bits/stdc++.h> 
using namespace std; 
  
int findMin(int a[], int beg, int end){  
    if(end < beg) 
        return a[0];  
  
    if(end==beg) 
        return a[beg];  
  
    int mid = beg + (end - beg)/2; 
  
    if(mid<end && a[mid + 1]<a[mid])  
        return a[mid + 1];  
  
    if(mid>beg && a[mid]<a[mid - 1])  
        return a[mid];  
  
    if(a[end]>a[mid])  
    return findMin(a, beg, mid - 1);  
    return findMin(a, mid + 1, end);  
}  
  
int main(){  
    int a[] = {5, 2, 3, 4}; 
    int n = sizeof(a)/sizeof(a[0]);  
    cout<<findMin(a, 0, n-1);  
    return 0;  
}
2

जावा प्रोग्राम

class MinSearch{ 
   
    static int findMin(int a[], int beg, int end){ 
        
        if(end < beg) 
            return a[0]; 
            
        if(end==beg) 
            return a[beg];
            
        int mid = beg + (end - beg)/2; 
        
        if(mid<end && a[mid + 1]<a[mid]) 
            return a[mid + 1]; 
        
        if(mid>beg && a[mid]<a[mid - 1]) 
            return a[mid]; 
        
        if(a[end]>a[mid]) 
            return findMin(a, beg, mid - 1); 
        return findMin(a, mid + 1, end); 
    }
        
    public static void main (String[] args){ 
        int a[] = {5, 2, 3, 4}; 
        int n = a.length; 
        System.out.println(findMin(a, 0, n-1)); 
    } 
}
2

जटिलता विश्लेषण

समय जटिलता

O (लॉग एन) जहाँ N इनपुट ऐरे में तत्वों की संख्या है। यहाँ हमने द्विआधारी खोज का उपयोग किया जो लॉगरिदमिक समय जटिलता लेता है। यह सब संभव है क्योंकि सरणी शुरू में क्रमबद्ध थी।

अंतरिक्ष जटिलता

ओ (1), इस दृष्टिकोण में भी निरंतर समय लगता है लेकिन एक पूरे के रूप में कार्यक्रम इनपुट को संग्रहीत करने के लिए आवश्यक स्थान के कारण O (N) स्थान लेता है।