מצא מינימום במערך ממוין מסובב  


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית מיקרוסופט מורגן סטנלי סמסונג 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.

אנו יכולים להשתמש בחיפוש ליניארי או פשוט לחצות את מערך הקלט פעם אחת ולמצוא את האלמנט הקטן ביותר במעבר יחיד. אנו פשוט נעבור על כל האלמנטים במערך ואם נמצא מספר שהוא פחות מהמינימום שלנו, אנו מעדכנים את תשובתנו.

ראה גם
עץ האינטרוולים

קופונים

תוכנית 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.

הגישה היעילה יותר תהיה שימוש בחיפוש בינארי מכיוון שמערך הקלט הוא מערך ממוין מסובב. כלומר, המערך ממוין אך הוא הסתובב בנקודה אחת. מאז חיפוש בינארי לוקח מורכבות זמן לוגריתמית. עדיף להשתמש בפתרון זה בהשוואה לאמור לעיל.

ראה גם
שאילתות לספירות של אלמנטים במערך עם ערכים בטווח נתון

קוד למציאת מינימום במערך הממוין המסובב באמצעות חיפוש בינארי

תוכנית 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) בגלל השטח הנדרש לאחסון הקלט.

1