Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में घूर्णन क्रमबद्ध सरणी II में खोज

मान लीजिए हमारे पास आरोही क्रम में क्रमबद्ध एक सरणी है। यह किसी अज्ञात पिवट पर घूमी हुई है। उदाहरण के लिए, यदि सरणी [0,0,1,2,2,5,6] जैसी है, तो यह [2,5,6,0,0,1,2] बन सकती है। हमारे पास खोजने के लिए एक लक्ष्य मान है। यदि वह सरणी में पाया जाता है, तो true लौटाएं, अन्यथा false लौटाएं। इसलिए यदि सरणी [2,5,6,0,0,1,2] जैसी है, और लक्ष्य 0 है, तो आउटपुट true होगा।

आइए चरण देखें -

  • low := 0 और high := सरणी का आकार
  • जबकि low < high
    • mid := low + (high - low)/2
    • यदि nums[mid] = target, तो true लौटाएं
    • यदि nums[low] = nums[mid] और nums[high - 1] = nums[mid], तो
      • low को 1 से बढ़ाएं और high को 1 से घटाएं, और अगले पुनरावृति के लिए जारी रखें
    • यदि nums[low] <= nums[mid], तो
      • यदि target >= nums[low] और target < nums[mid], तो high := mid, अन्यथा low := mid + 1
    • अन्यथा
      • यदि target <= nums[high - 1] और target > nums[mid], तो low := mid + 1, अन्यथा high := mid
  • false लौटाएं

उदाहरण

class Solution(object):
    def search(self, nums, target):
        low = 0
        high = len(nums)
        while low < high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                return True
            if nums[low] == nums[mid] and nums[high-1] == nums[mid]:
                low += 1
                high -= 1
                continue
            if nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid
                else:
                    low = mid+1
            else:
                if target <= nums[high-1] and target > nums[mid]:
                    low = mid+1
                else:
                    high = mid
        return False

ob1 = Solution()
print(ob1.search([2,5,6,0,0,1,2], 0))

इनपुट

[2,5,6,0,0,1,2] 0

आउटपुट

True
  1. पायथन में क्रमबद्ध सरणी को बाइनरी सर्च ट्री में बदलें पायथन में क्रमबद्ध सरणी को बाइनरी सर्च ट्री में बदलें

    मान लीजिए हमारे पास एक क्रमबद्ध सरणी A है। हमें एक ऊंचाई-संतुलित बाइनरी सर्च ट्री उत्पन्न करना है। इस समस्या में, एक ऊंचाई-संतुलित बाइनरी ट्री वास्तव में एक बाइनरी ट्री है जिसमें हर नोड के दो सबट्री की गहराई 1 से अधिक नहीं होती। मान लीजिए सरणी [-10, -3, 0, 5, 9] जैसी है। तो एक संभावित आउटपुट होगा:

  1. पायथन प्रोग्राम में इंसर्शन सॉर्ट पायथन प्रोग्राम में इंसर्शन सॉर्ट

    इस लेख में, हम पायथन 3.x में इंसर्शन सॉर्ट के कार्यान्वयन के बारे में सीखेंगे। या इससे पहले। एल्गोरिदम इनपुट एलिमेंट्स पर इटरेट करें और प्रत्येक इटरेशन में सॉर्टेड ऐरे को बढ़ाएं। वर्तमान एलिमेंट की तुलना सॉर्टेड ऐरे में उपलब्ध सबसे बड़े मान से करें। यदि वर्तमान एलिमेंट बड़ा है, तो यह एलिमेंट को उ

  1. पायथन प्रोग्राम: इंसर्शन सॉर्ट एल्गोरिदम पायथन प्रोग्राम: इंसर्शन सॉर्ट एल्गोरिदम

    इस लेख में, हम पायथन 3.x या उससे पहले के संस्करण में इंसर्शन सॉर्ट के कार्यान्वयन के बारे में जानेंगे।एल्गोरिदम1. प्रत्येक पुनरावृत्ति पर सॉर्टेड सरणी को बढ़ाते हुए इनपुट तत्वों पर पुनरावृति करें।2. वर्तमान तत्व की तुलना सॉर्टेड सरणी में उपलब्ध सबसे बड़े मान से करें।3. यदि वर्तमान तत्व बड़ा है, तो इ