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

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

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

• निम्न:=0 और उच्च:=सरणी का आकार
• जबकि कम <उच्च
  • मध्य :=निम्न + (उच्च-निम्न)/2
  • यदि अंक [मध्य] =लक्ष्य है, तो सही लौटें
  • यदि अंक [निम्न] =अंक [मध्य] और अंक [उच्च -1] =अंक [मध्य], तो
    • निम्न 1 से बढ़ाएं और 1 से उच्च घटाएं, और अगले पुनरावृत्ति के लिए जारी रखें
  • यदि अंक [कम] <=अंक [मध्य], तो
    • यदि लक्ष्य>=nums[low] और लक्ष्य &miinus; अंक [मध्य], फिर उच्च:=मध्य, अन्यथा निम्न:=मध्य + 1
  • अन्यथा
    • यदि लक्ष्य <=अंक [उच्च -1] और लक्ष्य> अंक [मध्य], तो निम्न:=मध्य + 1, अन्यथा उच्च:=मध्य
• झूठी वापसी

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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