C++ में घूर्णित क्रमबद्ध सरणी II में खोज (Search in Rotated Sorted Array 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

इनपुट

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

आउटपुट

true