ข้อ 55 · LC162 Find Peak Element (หายอด peak) 🟡

โจทย์ (LC162): peak element (สมาชิกที่เป็นยอด) คือสมาชิกที่มีค่ามากกว่า neighbor (เพื่อนบ้าน) ทั้งสองข้าง กำหนด array จำนวนเต็ม nums แบบ 0-indexed ที่ nums[i] ไม่เท่ากับ nums[i+1] เสมอ ให้หา index ของ peak element ใด ๆ แล้ว return index นั้น โดยถือว่าขอบนอกของ array ทั้งสองฝั่งมีค่าเท่ากับลบอนันต์ (nums[-1] = nums[n] = -∞) ถ้ามีหลาย peak ให้ return index ของตัวไหนก็ได้ ต้องเขียนอัลกอริทึมที่รันด้วยเวลา O(log n)

แนวทาง — ต้องใช้อะไร & คิดยังไง

โครงสร้างที่ใช้: binary search แบบดูทิศชัน แม้ array ไม่ได้ sort แต่ยังใช้ binary search ได้ compare (เทียบ) nums[mid] กับ nums[mid+1] ถ้ากำลังขาขึ้น (mid น้อยกว่า mid+1) peak อยู่ทางขวาแน่ ๆ ถ้ากำลังขาลง peak อยู่ทางซ้าย (รวม mid เอง)

คิดแบบง่าย/ช้าก่อน: วิธี naive คือ iterate (วน) ทุกตัวหาจุดที่มากกว่า neighbor ทั้งสอง เป็น O(n) แต่โจทย์บังคับ O(log n) เพราะขอบนอกเป็นลบอนันต์ การเดินขึ้นเนินไปเรื่อย ๆ ต้องเจอ peak เสมอ เราจึงตัดครึ่งไปทางที่ชันขึ้นได้

1. initialize (ตั้งค่าเริ่มต้น) lo = 0, hi = len(nums) - 1
2. ระหว่าง lo < hi: compute mid
3. ถ้า nums[mid] < nums[mid+1] กำลังขาขึ้น peak อยู่ทางขวา ตั้ง lo = mid + 1 (mid ไม่ใช่ peak แน่)
4. ไม่งั้น (ขาลงหรือเท่า) peak อยู่ทางซ้ายรวม mid เอง ตั้ง hi = mid; จบ loop lo == hi คือตำแหน่ง peak

ไล่ทีละสเต็ป

จำลอง nums = [1,2,1,3,5,6,4]:

def find_peak_element(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            # กำลังขาขึ้น ยอดต้องอยู่ทางขวา (mid ไม่ใช่ยอดแน่)
            lo = mid + 1
        else:
            # กำลังขาลงหรือเท่า ยอดอยู่ทางซ้าย รวม mid ด้วย
            hi = mid
    return lo   # lo == hi คือตำแหน่งยอด

print(find_peak_element([1, 2, 3, 1]))         # 2
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))  # 5

2
5