একটি অ্যাসেন্ডিং অর্ডারে সর্টেড অ্যারে রোটেট করা আছে (পিভট অজানা)। উদাহরণ: [0,0,1,2,2,5,6] -> [2,5,6,0,0,1,2]। একটি টার্গেট ভ্যালু সার্চ করতে হবে। পাওয়া গেলে true, না পেলে false।
অ্যারে [2,5,6,0,0,1,2], টার্গেট 0 হলে আউটপুট true।
সমাধানের ধাপসমূহ
- low := 0, high := len(nums)
- যখন low < high:
- mid := low + (high - low) // 2
- যদি nums[mid] == target: true রিটার্ন
- যদি nums[low] == nums[mid] এবং nums[high-1] == nums[mid]: low++, high--, কন্টিনিউ
- যদি nums[low] <= nums[mid]:
- যদি target >= nums[low] এবং target < nums[mid]: high = mid, অন্যথায় low = mid + 1
- অন্যথায়:
- যদি target <= nums[high-1] এবং target > nums[mid]: low = mid + 1, অন্যথায় high = mid
- false রিটার্ন
উদাহরণ
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
