रोटेटिड सॉर्टेड ऐरे क्या है?

एक क्रमबद्ध सरणी पर विचार करें, उदाहरण के लिए:

[1, 2, 3, 4, 5, 6]

अब, यदि इस सरणी को किसी धुरी पर घुमाया जाता है, मान लीजिए सूचकांक 3 पर, तो यह बन जाएगा:

[4, 5, 6, 1, 2, 3]

ध्यान दें कि सरणी अभी भी क्रमबद्ध है, लेकिन यह दो भागों में विभाजित है। हमारा लक्ष्य ऐसे सरणियों में लक्ष्य मान को कुशलतापूर्वक खोजना है।

खोज रणनीति

घुमाए गए क्रमबद्ध सरणी में खोज करने के लिए, हमें यह करना होगा:

1. धुरी ढूंढें: धुरी वह बिंदु है जहां सरणी बड़े से छोटे मानों में परिवर्तित होती है।
2. बाइनरी खोज: एक बार जब हमें धुरी मिल जाती है, तो हम सरणी के उपयुक्त आधे हिस्से पर बाइनरी खोज का उपयोग कर सकते हैं।

चरण-दर-चरण कोड स्पष्टीकरण

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: "   result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot   1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid   1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 





  
  
  संहिता की व्याख्या



खोज():

यह फ़ंक्शन घुमाए गए क्रमबद्ध सरणी में लक्ष्य की खोज के लिए जिम्मेदार है।
सबसे पहले, हम searchPivot() फ़ंक्शन का उपयोग करके pivot ढूंढते हैं।
धुरी की स्थिति के आधार पर, हम फिर तय करते हैं कि बाइनरी खोज का उपयोग करके सरणी के किस आधे हिस्से को खोजना है।


द्विआधारी खोज():

क्रमबद्ध उप-सरणी में लक्ष्य खोजने के लिए एक मानक बाइनरी खोज एल्गोरिदम।
हम आरंभ और अंत सूचकांकों को परिभाषित करते हैं और खोज स्थान को उत्तरोत्तर सीमित करते हैं।


searchPivot():

यह फ़ंक्शन धुरी बिंदु (वह स्थान जहां सरणी घूमती है) की पहचान करता है।
धुरी वह सूचकांक है जहां क्रमबद्ध क्रम "टूटा हुआ" होता है (यानी, सरणी उच्च मान से निम्न मान पर जाती है)।
यदि कोई धुरी नहीं मिलती है, तो इसका मतलब है कि सरणी घुमाई नहीं गई थी, और हम नियमित बाइनरी खोज कर सकते हैं।


  
  
  एल्गोरिदम कैसे काम करता है


[4, 5, 6, 1, 2, 3] जैसी सरणी के लिए:

• धुरी सूचकांक 2 पर है (6 सबसे बड़ा है, और इसके बाद 1 है, सबसे छोटा)।
• हम इस धुरी का उपयोग सरणी को दो भागों में विभाजित करने के लिए करते हैं: [4, 5, 6] और [1, 2, 3]।
• यदि लक्ष्य पहले तत्व (इस मामले में 4) से बड़ा या उसके बराबर है, तो हम बाएं आधे हिस्से को खोजते हैं। अन्यथा, हम दायां आधा खोजते हैं।

यह विधि सुनिश्चित करती है कि हम मानक बाइनरी खोज के समान O(log n) की समय जटिलता प्राप्त करते हुए कुशलतापूर्वक खोज करते हैं।

निष्कर्ष

रोटेटेड सॉर्टेड एरेज़ एक सामान्य साक्षात्कार प्रश्न हैं और बाइनरी खोज की आपकी समझ को गहरा करने के लिए एक उपयोगी चुनौती है। पिवट को ढूंढकर और तदनुसार अपनी बाइनरी खोज को अनुकूलित करके, हम कुशलतापूर्वक लघुगणक समय में सरणी के माध्यम से खोज कर सकते हैं।

यदि आपको यह लेख उपयोगी लगा, तो बेझिझक मेरे साथ लिंक्डइन पर जुड़ें या टिप्पणियों में अपने विचार साझा करें! हैप्पी कोडिंग!