Знайти мінімум у обертаному відсортованому масиві


Рівень складності Легко
Часто запитують у саман Амазонка Microsoft Morgan Stanley Samsung Snapdeal Times Інтернет
масив Двійковий пошук Розділяй і володарюй Пошук

Постановка проблеми

“Знайти мінімум у обертаному відсортованому масиві” говорить про те, що вам надано відсортований масив розміром 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 (N),  оскільки ми здійснили обхід усіх елементів масиву, що дозволило нам досягти лінійної часової складності.

Складність простору

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.

Більш ефективним підходом буде використання двійкового пошуку, оскільки вхідний масив - це повернутий відсортований масив. Тобто масив сортується, але його обертали в одній точці. Оскільки двійковий пошук вимагає логарифмічної часової складності. Краще використовувати це рішення порівняно з наведеним вище.

Код для пошуку мінімуму в оберненому відсортованому масиві за допомогою двійкового пошуку

Програма С ++

#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) простір через простір, необхідний для зберігання вхідних даних.