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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• निम्न:=0 और उच्च:=सरणी की लंबाई
• जबकि कम <उच्च
  • मध्य को मध्य के रूप में खोजें:=निम्न + (उच्च-निम्न)/2
  • अगर गिरफ्तारी [मध्य] =लक्ष्य है, तो मध्य में वापस आएं
  • अगर गिरफ्तारी [कम] <=गिरफ्तारी [मध्य]
    • यदि लक्ष्य>=गिरफ्तारी [निम्न] और लक्ष्य <गिरफ्तारी [मध्य], तो उच्च :=मध्य, अन्यथा निम्न :=मध्य + 1
  • अन्यथा
    • यदि लक्ष्य <=गिरफ्तारी [उच्च -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 mid
         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 -1
ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))

इनपुट

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

आउटपुट

5