ફેરવેલ સortedર્ટ થયેલ એરેમાં ન્યૂનતમ શોધો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન માઈક્રોસોફ્ટ મોર્ગન સ્ટેન્લી સેમસંગ સ્નેપડીલ ટાઇમ્સ ઇન્ટરનેટ
અરે દ્વિસંગી શોધ વિભાજીત અને વિજય શોધી રહ્યું છે

સમસ્યા નિવેદન

“ફેરવો ન્યૂનતમ ઇન રોટેટેડ સortedર્ટડ એરે” જણાવે છે કે તમને કદ n ની સortedર્ટ એરે આપવામાં આવે છે જે કેટલાક ઇન્ડેક્સ પર ફેરવવામાં આવે છે. માં ન્યૂનતમ તત્વ શોધો એરે.

ઉદાહરણ

ફેરવેલ સortedર્ટ થયેલ એરેમાં ન્યૂનતમ શોધો

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

સમજૂતી: જો આપણે સrayર્ટ કરેલા ક્રમમાં એરે ગોઠવીશું તો તે [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.

બાઈનરી સર્ચનો ઉપયોગ કરવાનો વધુ અસરકારક અભિગમ હશે કારણ કે ઇનપુટ એરે એક રોટેટેડ સortedર્ટ થયેલ એરે છે. તે એરે સortedર્ટ થયેલ છે પરંતુ તે એક જ બિંદુએ ફેરવવામાં આવ્યું હતું. દ્વિસંગી શોધ લોગાર્થોમિક સમય જટિલતા લે છે. ઉપરોક્ત એકની તુલનામાં આ સોલ્યુશનનો ઉપયોગ કરવો વધુ સારું છે.

દ્વિસંગી શોધનો ઉપયોગ કરીને રોટેટેડ સortedર્ટ થયેલ એરેમાં ઓછામાં ઓછું શોધવા માટેનો કોડ

સી ++ પ્રોગ્રામ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (લોગ એન) જ્યાં એન એ ઇનપુટ એરેમાં તત્વોની સંખ્યા છે. અહીં અમે દ્વિસંગી શોધનો ઉપયોગ કર્યો જે લોગરીધમિક સમયની જટિલતાને લે છે. આ બધું શક્ય છે કારણ કે પ્રારંભમાં એરે સ sર્ટ કરવામાં આવી હતી.

અવકાશ જટિલતા

ઓ (1), આ અભિગમ પણ સતત સમય લે છે પરંતુ ઇનપુટ સ્ટોર કરવા માટે જરૂરી જગ્યાને કારણે પ્રોગ્રામ સમગ્ર રીતે O (N) જગ્યા લે છે.