சுழற்றப்பட்ட வரிசை வரிசையில் குறைந்தபட்சத்தைக் கண்டறியவும்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் மைக்ரோசாப்ட் மோர்கன் ஸ்டான்லி சாம்சங் Snapdeal டைம்ஸ் இணையம்
அணி பைனரி தேடல் பிரித்து வெல்லுங்கள் தேடி

சிக்கல் அறிக்கை  

"சுழற்றப்பட்ட வரிசைப்படுத்தப்பட்ட வரிசையில் குறைந்தபட்சத்தைக் கண்டுபிடி" என்பது உங்களுக்கு ஒரு வரிசைப்படுத்தப்பட்ட வரிசை 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.

நாம் நேரியல் தேடலைப் பயன்படுத்தலாம் அல்லது உள்ளீட்டு வரிசையை ஒரு முறை பயணிக்கலாம் மற்றும் ஒற்றை பயணத்தில் மிகச்சிறிய உறுப்பைக் காணலாம். வரிசையில் உள்ள அனைத்து உறுப்புகளையும் நாம் வெறுமனே சுழற்றுவோம், மேலும் நமது குறைந்தபட்சத்தை விடக் குறைவான எண்ணைக் கண்டால், எங்கள் பதிலைப் புதுப்பிப்போம்.

மேலும் காண்க
இடைவெளி மரம்

குறியீடு

சுழற்றப்பட்ட வரிசைப்படுத்தப்பட்ட வரிசையில் குறைந்தபட்சம் கண்டுபிடிக்க சி ++ நிரல்

#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.

உள்ளீட்டு வரிசை ஒரு சுழற்றப்பட்ட வரிசைப்படுத்தப்பட்ட வரிசை என்பதால் பைனரி தேடலைப் பயன்படுத்துவது மிகவும் திறமையான அணுகுமுறையாக இருக்கும். அது வரிசை வரிசைப்படுத்தப்பட்டுள்ளது, ஆனால் அது ஒரு புள்ளியில் சுழற்றப்பட்டது. பைனரி தேடல் மடக்கை நேர சிக்கலை எடுக்கும் என்பதால். மேலே உள்ளதை ஒப்பிடும்போது இந்த தீர்வைப் பயன்படுத்துவது நல்லது.

மேலும் காண்க
கொடுக்கப்பட்ட வரம்பில் மதிப்புகள் கொண்ட வரிசை கூறுகளின் எண்ணிக்கைக்கான வினவல்கள்

பைனரி தேடலைப் பயன்படுத்தி சுழற்றப்பட்ட வரிசைப்படுத்தப்பட்ட வரிசையில் குறைந்தபட்சம் கண்டுபிடிக்க குறியீடு

சி ++ திட்டம்

#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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (பதிவு என்) N என்பது உள்ளீட்டு வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. இங்கே நாம் பைனரி தேடலைப் பயன்படுத்தினோம், இது மடக்கை நேர சிக்கலை எடுக்கும். வரிசை ஆரம்பத்தில் வரிசைப்படுத்தப்பட்டதால் இவை அனைத்தும் சாத்தியமாகும்.

விண்வெளி சிக்கலானது

ஓ (1), இந்த அணுகுமுறை நிலையான நேரத்தையும் எடுக்கும், ஆனால் உள்ளீடு சேமிக்க தேவையான இடம் இருப்பதால் நிரல் ஒட்டுமொத்தமாக O (N) இடத்தை எடுக்கும்.

1