পাইথনে সাজানো অ্যারেতে এলিমেন্টের প্রথম এবং শেষ অবস্থান খুঁজুন

ধরুন আমাদের কাছে পূর্ণসংখ্যা A এর একটি অ্যারে রয়েছে। এটি ঊর্ধ্বক্রম অনুসারে সাজানো হয়েছে, আমাদের একটি নির্দিষ্ট লক্ষ্য মানের শুরু এবং শেষ অবস্থান খুঁজে বের করতে হবে। যখন অ্যারেতে টার্গেট পাওয়া যায় না, [-1, -1] রিটার্ন করুন। সুতরাং যদি অ্যারে হয় [2,2,2,3,4,4,4,4,5,5,6], এবং লক্ষ্য 4 হয়, তাহলে আউটপুট হবে [4,7]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• প্রাথমিকভাবে res :=[-1,-1], সেট কম :=0, উচ্চ :=অ্যারের দৈর্ঘ্য
• যদিও কম <উচ্চ
  • মধ্য :=নিম্ন + (উচ্চ – নিম্ন)/2
  • যদি A[মিড] টার্গেট হয়, তাহলে
    • উচ্চ :=মধ্য, রেস[0] :=মধ্য এবং রেস[1] :=মধ্য
  • অন্যথায় যখন A[mid]
• যদি res[0] =-1 হয়, তাহলে রিটার্ন রিটার্ন করুন
• নিম্ন :=রেস[0] + 1, উচ্চ :=সংখ্যার দৈর্ঘ্য
• যদিও কম <উচ্চ
  • মধ্য :=নিম্ন + (উচ্চ – নিম্ন)/2
  • যদি A[মিড] টার্গেট হয়, তাহলে
    • নিম্ন :=মধ্য + 1, রেস[1] :=মধ্য
  • অন্যথায় যখন A[mid]
• রিটার্ন রিটার্ন

উদাহরণ(পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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]