گھمائے گئے ترتیب والے صف میں کم سے کم ڈھونڈیں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون مائیکروسافٹ مارگن سٹینلی سیمسنگ 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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

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

جاوا پروگرام

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 ان پٹ صف میں موجود عناصر کی تعداد ہے۔ یہاں ہم نے بائنری تلاش کا استعمال کیا جو لاگارتھمک وقت کی پیچیدگی لیتی ہے۔ یہ سب ممکن ہے کیونکہ ابتدائی طور پر سرنی ترتیب دی گئی تھی۔

خلائی پیچیدگی

O (1) ، اس نقطہ نظر کو مستقل وقت بھی لگتا ہے لیکن مجموعی طور پر پروگرام میں ان پٹ کو محفوظ کرنے کے لئے درکار جگہ کی وجہ سے O (N) جگہ لیتا ہے۔