पायथन में क्रमबद्ध सरणी में तत्व की पहली और अंतिम स्थिति खोजें

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

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

• आरंभ में res :=[-1,-1], निम्न सेट करें:=0, उच्च:=सरणी A की लंबाई
• जबकि कम <उच्च
  • मध्य :=निम्न + (उच्च-निम्न)/2
  • यदि A[मध्य] लक्ष्य है, तो
    • उच्च:=मध्य, रेस[0]:=मध्य और रेस[1]:=मध्य
  • अन्यथा जब A[मध्य] <लक्ष्य, फिर निम्न :=मध्य + 1, अन्य उच्च :=मध्य
• अगर res[0] =-1, तो res वापस करें
• निम्न:=रेस[0] + 1, उच्च:=अंकों की लंबाई
• जबकि कम <उच्च
  • मध्य :=निम्न + (उच्च-निम्न)/2
  • यदि A[मध्य] लक्ष्य है, तो
    • निम्न:=मध्य + 1, रेस[1]:=मध्य
  • अन्यथा जब A[मध्य] <लक्ष्य, फिर निम्न :=मध्य + 1, अन्य उच्च :=मध्य
• रिटर्न रेस

उदाहरण (पायथन)

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

class Solution(object):
   def searchRange(self, nums, target):
      res = [-1,-1]
      low = 0
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            high = mid
            res[0]=mid
            res[1]=mid
         elif nums[mid]<target:
            low = mid+1
         else:
            high = mid
      if res[0] == -1:
         return res
      low = res[0]+1
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            low = mid+1
            res[1] = mid
         elif nums[mid] < target:
            low = mid + 1
         else:
            high = mid
      return res
ob1 = Solution()
print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))

इनपुट

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

आउटपुट

[5, 8]