ধরুন আমাদের একটি অ্যারেতে পিক এলিমেন্ট খুঁজে বের করতে হবে। পিক এলিমেন্ট হল এমন একটি উপাদান যা তার প্রতিবেশীদের থেকে বড়। ধরুন আমাদের একটি ইনপুট অ্যারে সংখ্যা আছে, যেখানে nums[i] ≠ nums[i+1], একটি পিক এলিমেন্ট অনুসন্ধান করুন এবং এর সূচকটি ফেরত দিন। অ্যারে একাধিক পিক উপাদান ধারণ করতে পারে, সেক্ষেত্রে সূচীটিকে শীর্ষ উপাদানগুলির যেকোনো একটিতে ফিরিয়ে দিন। আমরা কল্পনা করতে পারি যে সংখ্যাগুলি[-1] =সংখ্যাগুলি [n] =-∞৷ সুতরাং যদি অ্যারেটি [1,2,1,3,5,6,4] এর মত হয়, তাহলে সর্বোচ্চ উপাদান 1 বা 5 হওয়া উচিত।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- নিম্ন :=0 এবং উচ্চ :=অ্যারের শেষ সূচক, n :=অ্যারের আকার, উত্তর :=অসীম
- যখন কম <=উচ্চ
- মধ্য :=নিম্ন + (উচ্চ - নিম্ন)/2
- যদি mid – 1>=0 এবং nums[mid – 1] <=nums[mid], তারপর low :=mid, অন্যথায় high :=mid - 1
- কম রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution(object): def findPeakElement(self, nums): low = 0 high = len(nums)-1 while low<high: mid = low + (high - low+1)//2 if (mid-1>=0 and nums[mid-1]<=nums[mid]): low = mid else: high = mid-1 return nums[low+1] ob1 = Solution() print(ob1.findPeakElement([15,35,85,96,5,6,8,12]))
ইনপুট
[15,35,85,96,5,6,8,12]
আউটপুট
5