สมมติว่าเราต้องหาพีคอิลิเมนต์ในอาร์เรย์ องค์ประกอบสูงสุดเป็นองค์ประกอบที่มากกว่าเพื่อนบ้าน สมมติว่าเรามีอินพุตอาร์เรย์ nums โดยที่ nums[i] ≠ nums[i+1] ค้นหาองค์ประกอบพีคและส่งคืนดัชนี อาร์เรย์สามารถเก็บอิลิเมนต์พีคได้หลายรายการ ในกรณีนี้ ให้ส่งคืนดัชนีไปยังอิลิเมนต์พีคตัวใดตัวหนึ่ง เราสามารถจินตนาการได้ว่า nums[-1] =nums[n] =-∞ ดังนั้นหากอาร์เรย์เป็นเหมือน [1,2,1,3,5,6,4] อิลิเมนต์พีคควรเป็น 1 หรือ 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ต่ำ :=0 และสูง :=ดัชนีสุดท้ายของอาร์เรย์ n :=ขนาดของอาร์เรย์ ans :=อินฟินิตี้
- ในขณะที่ต่ำ <=สูง
- กลาง :=ต่ำ + (สูง - ต่ำ)/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
