C++-এ রোটেটেড সর্টেড অ্যারেতে মিনিমাম খুঁজে বের করা II (Find Minimum in Rotated Sorted Array II)

রোটেটেড সর্টেড অ্যারেতে মিনিমাম (ডুপ্লিকেট সহ)

একটি সর্টেড অ্যারে কোনো পিভট পয়েন্টে রোটেট করা হয়েছে। ডুপ্লিকেট উপাদান থাকতে পারে। ন্যূনতম উপাদানটি খুঁজে বের করতে হবে।

উদাহরণ: [4,5,5,5,6,8,2,3,4] → ন্যূনতম: ২

সমাধানের পদ্ধতি (মডিফাইড বাইনারি সার্চ)

• বাইনারি সার্চের মতো low, high, mid ব্যবহার করুন
• যদি arr[low] < arr[mid]: বাম অংশ সর্টেড, মিনিমাম বামে বা মিডে → ans = min(arr[low], search(mid, high))
• যদি arr[high] > arr[mid]: ডান অংশ সর্টেড, মিনিমাম মিডে বা ডানে → ans = min(arr[mid], search(low, mid))
• যদি arr[low] == arr[mid]: low++ করে ডুপ্লিকেট স্কিপ করুন
• যদি arr[high] == arr[mid]: high-- করে ডুপ্লিকেট স্কিপ করুন
• বেস্ট কেস O(log n), ওয়ার্স্ট কেস O(n) (সব ডুপ্লিকেট হলে)

C++ কোড উদাহরণ

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

আউটপুট

2