Find Peak Element ใน Python

Peak element คือค่าที่มากกว่าเพื่อนบ้านทั้งสองข้าง (หรือข้างเดียวที่ขอบ) ให้คืน index ของ peak ใดก็ได้

ตัวอย่าง

Input: [1,2,1,3,5,6,4]
Peaks: index 1 (ค่า 2) หรือ index 5 (ค่า 6)

อัลกอริทึม Binary Search (O(log n))

เนื่องจาก nums[i] ≠ nums[i+1] เราสามารถ binary search ได้:

1. mid = (low+high)//2
2. ถ้า nums[mid] < nums[mid+1] → peak อยู่ขวา (low = mid+1)
3. มิฉะนั้น → peak อยู่ซ้ายรวม mid (high = mid)
4. จน low == high → นั่นคือ peak

โค้ด

class Solution:
    def findPeakElement(self, nums):
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) // 2
            if nums[mid] < nums[mid + 1]:
                low = mid + 1
            else:
                high = mid
        return low

# ทดสอบ
sol = Solution()
print(sol.findPeakElement([1,2,1,3,5,6,4]))      # 5 (ค่า 6)
print(sol.findPeakElement([15,35,85,96,5,6,8,12])) # 3 (ค่า 96)

สรุป

Binary search หา peak ได้ใน O(log n) โดยอาศัยเงื่อนไข adjacent ไม่เท่ากัน