পাইথনে ঘূর্ণিত সাজানো অ্যারে 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
  • যদি nums[mid] =টার্গেট, তারপর true রিটার্ন করুন
  • যদি nums[low] =nums[mid] এবং nums[high - 1] =nums[mid], তাহলে
    • 1 দ্বারা কম বাড়ান এবং 1 দ্বারা উচ্চ হ্রাস করুন এবং পরবর্তী পুনরাবৃত্তির জন্য চালিয়ে যান
  • যদি nums[low] <=nums[mid], তারপর
    • যদি লক্ষ্য>=সংখ্যা [নিম্ন] এবং লক্ষ্য &মাইনাস; সংখ্যা[মধ্য], তারপর উচ্চ :=মধ্য, অন্যথায় নিম্ন :=মধ্য + 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