पायथन में पीक एलिमेंट ढूंढें

मान लीजिए हमें एक ऐरे में पीक एलिमेंट ढूंढना है। पीक एलिमेंट वह एलिमेंट है जो अपने पड़ोसियों से बड़ा है। मान लीजिए हमारे पास एक इनपुट ऐरे nums है, जहां nums[i] ≠ nums[i+1], एक पीक एलिमेंट खोजें और उसका इंडेक्स लौटाएं। ऐरे में कई पीक एलिमेंट हो सकते हैं, उस स्थिति में किसी एक पीक एलिमेंट का इंडेक्स लौटाएं। हम कल्पना कर सकते हैं कि nums[-1] = nums[n] = -∞। इसलिए यदि ऐरे [1,2,1,3,5,6,4] जैसा है, तो पीक एलिमेंट्स 1 या 5 होने चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• low := 0 और high := ऐरे का अंतिम इंडेक्स, n := ऐरे का आकार, ans := infinity
• जब तक low <= high
  • mid := low + (high - low) / 2
  • यदि mid - 1 >= 0 और nums[mid - 1] <= nums[mid], तो low := mid, अन्यथा high := mid - 1
• low लौटाएं

यह बाइनरी सर्च का उपयोग करके O(log n) समय में पीक ढूंढता है।

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

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