পাইথনে ঘূর্ণিত সাজানো অ্যারে অনুসন্ধান করুন

বিবেচনা করুন আমাদের একটি অ্যারে ঊর্ধ্বক্রম অনুসারে সাজানো আছে, এবং এটি আপনার আগে থেকে অজানা কিছু পিভটে ঘোরানো হয়েছে৷ উদাহরণস্বরূপ, [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
- যদি arr[mid] =টার্গেট, তারপর mid রিটার্ন
- যদি arr[low] <=arr[mid]
  - যদি টার্গেট>=arr[low] এবং টার্গেট
- অন্যথায়
  - যদি লক্ষ্য <=arr[high - 1] এবং target> arr[mid] হয়, তারপর low :=mid + 1, অন্যথায় high :=mid
রিটার্ন -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