Намерете минимум в завъртян сортиран масив


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка Microsoft Morgan Stanley Samsung Snapdeal Times Интернет
Array Двоично търсене Разделяй и владей Търсене

Декларация за проблема

„Намиране на минимум в завъртян сортиран масив“ заявява, че ви се дава сортиран масив с размер 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

Програма Java за намиране на минимум в завъртян сортиран масив

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

Анализ на сложността

Сложност във времето

НА),  защото прекосихме всички елементи в масива, което ни позволи да постигнем линейна времева сложност.

Сложност на пространството

O (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

Програма Java

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) където N е броят на елементите във входния масив. Тук използвахме двоично търсене, което отнема логаритмична времева сложност. Всичко това е възможно, защото масивът първоначално е сортиран.

Сложност на пространството

O (1), този подход отнема и постоянно време, но програмата като цяло заема O (N) пространство поради пространството, необходимо за съхранение на входа.