सॉर्ट किए गए घुमाए गए सरणी में एक तत्व खोजें


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग ByteDance ईबे Expedia Facebook गूगल माइक्रोसॉफ्ट Nvidia ओरेकल पेपैल Paytm VMware वॉलमार्ट लैब्स Zillow
ऐरे द्विआधारी खोज

छँटाई में खोजा घुमाया सरणी समस्या हमने एक क्रमबद्ध और घुमाया हुआ सरणी और एक तत्व दिया है, यह जाँचें कि क्या दिया गया तत्व सरणी में मौजूद है या नहीं।

उदाहरण

निवेश
अंक [] = {२, ५, ६, ०, ०, १, २}
लक्ष्य = ०
उत्पादन
<strong>उद्देश्य</strong>

सॉर्ट किए गए घुमाए गए सरणी में एक तत्व खोजें

निवेश
अंक [] = {२, ५, ६, ०, ०, १, २}
लक्ष्य = ०
उत्पादन
असत्य

छाँटे गए घुमाए गए सरणी में एक तत्व की खोज के लिए Naive दृष्टिकोण

सरणी में रेखीय रूप से ट्रैवर्स और लक्ष्य मान की खोज करें।

  1. I = 0 से n (शामिल नहीं) के लिए एक लूप चलाएँ, जहां n सरणी में तत्वों की संख्या है।
  2. प्रत्येक पुनरावृत्ति पर, जाँचें कि क्या अंक [i] एक लक्ष्य मान के बराबर है या नहीं। यदि यह समान है, तो सही लौटें, अन्यथा अगले तत्व के लिए जारी रखें।
  3. यदि कोई तत्व लक्ष्य मान के बराबर नहीं है, तो गलत लौटें।

जावा कोड

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target) {
        int n = nums.length;
        // Traverse the given array and search for the target value
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;

        System.out.println(searchTarget(nums, target));

        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target));
    }
}
true
false

C ++ कोड

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int n) {
    // Traverse the given array and search for the target value
    for (int i = 0; i < n; i++) {
        if (nums[i] == target)
            return true;
    }
    return false;
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

सॉर्ट किए गए घुमाए गए सरणी में एक तत्व की खोज के लिए जटिलता विश्लेषण

समय जटिलता = पर)
अंतरिक्ष जटिलता = ओ (1) 
जहाँ n सरणी में तत्वों की संख्या है।

ऑप्टिमाइज्ड एप्रोच इन सर्च ए एलीमेंट इन सॉर्टेड रोटेटेड एरे

सरणी में डुप्लिकेट हो सकते हैं, इसलिए सरणी को दो सॉर्ट किए गए सरणियों में विभाजित करने का विचार काम नहीं करेगा।

एरे के शुरुआती इंडेक्स को l और एंडिंग इंडेक्स h होने दें।

  1. मध्य का पता लगाएं, के रूप में मध्य = (एल + एच) / 2।
  2. यदि गिरफ्तारी [मध्य] मूल्य लक्ष्य के बराबर है, तो सही लौटें।
  3. यदि गिरफ्तारी [l] गिरफ्तारी के बराबर है [h] गिरफ्तारी के बराबर है [मध्य], तो वेतन वृद्धि l और वेतन वृद्धि h है।
  4. अगर गिरफ्तारी [l] से कम है या गिरफ्तारी के बराबर है [मध्य], तो बाएं आधे को छांटा जाता है, अगर लक्ष्य छोड़े गए बाएं आधे की सीमा में है, तो बाएं आधे में खोज करें और दाएं आधे में खोजें।
  5. यदि उपरोक्त स्थिति सही नहीं है, तो दाईं आधी, मध्य से एच तक की छंटनी की जाती है, यदि लक्ष्य सही दाएं आधे की सीमा में है, तो बाएं आधे में दाएं आधे में खोजें।

जावा कोड

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target, int l, int h) {
        // Index out of bound, element does not exist
        if (l > h)
            return false;
        // Find the middle element
        int mid = (l + h) / 2;
        // If this is the target element, return true
        if (nums[mid] == target) {
            return true;
        }
        // If nums[l] = nums[h] = nums[mid], increment l and decrement h
        if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
            return searchTarget(nums, target, l + 1, h - 1);
        }
        
        // If nums[l] <= nums[mid], left half is sorted
        if (nums[l] <= nums[mid]) {
            // If the target lies in the first half, search in first half
            if (target >= nums[l] && target <= nums[mid]) {
                return searchTarget(nums, target, l, mid - 1);
            }
            // Else search in second half
            return searchTarget(nums, target, mid + 1, h);
        }
        
        // If first half is not sorted, then second half is sorted
        // If the target is present in the second half, search in second half
        if (target >= nums[mid] && target <= nums[h]) {
            return searchTarget(nums, target, mid + 1, h);
        }
        // Else search in the first half
        return searchTarget(nums, target, l, mid - 1);
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;
        
        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
        
        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
    }
}
true
false

C ++ कोड

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int l, int h) {
    // Index out of bound, element does not exist
    if (l > h)
        return false;
    // Find the middle element
    int mid = (l + h) / 2;
    // If this is the target element, return true
    if (nums[mid] == target)
        return true;
    // If nums[l] = nums[h] = nums[mid], increment l and decrement h
    if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
        return searchTarget(nums, target, l + 1, h - 1);
    }
    
    // If nums[l] <= nums[mid], left half is sorted
    if (nums[l] <= nums[mid]) {
        // If the target lies in the first half, search in first half
        if (target >= nums[l] && target <= nums[mid]) {
            return searchTarget(nums, target, l, mid - 1);
        }
        // Else search in second half
        return searchTarget(nums, target, mid + 1, h);
    }

    // If first half is not sorted, then second half is sorted
    // If the target is present in the second half, search in second half
    if (target >= nums[mid] && target <= nums[h]) {
        return searchTarget(nums, target, mid + 1, h);
    }
    // Else search in the first half
    return searchTarget(nums, target, l, mid - 1);
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

सॉर्ट किए गए घुमाए गए सरणी में एक तत्व की खोज के लिए जटिलता विश्लेषण

समय जटिलता = O (लॉग एन)
अंतरिक्ष जटिलता = ओ (1) 
जहाँ n सरणी में तत्वों की संख्या है।

संदर्भ