บทความนี้สาธิตการหา peak element ในอาร์เรย์ (ค่าที่มากกว่าทั้งซ้ายและขวา) ใช้ binary search แบบปรับเปลี่ยน
ตัวอย่าง
arr = [3, 6, 7, 9, 8, 2, 5] -> peak = 9
ตัวอย่างโค้ด
const arr = [3, 6, 7, 9, 8, 2, 5];
const greaterThanAdjacent = (arr = [], start = 0, end = arr.length) => {
let mid = start + Math.floor((end - start) / 2);
let curr = arr[mid];
let prev = mid - 1 < 0 ? -Infinity : arr[mid - 1];
let next = mid + 1 > arr.length - 1 ? -Infinity : arr[mid + 1];
if (curr > prev && curr > next) {
return arr[mid];
}
if (curr < next) {
return greaterThanAdjacent(arr, mid + 1, end);
}
if (curr > next) {
return greaterThanAdjacent(arr, start, mid - 1);
}
return null;
};
console.log(greaterThanAdjacent(arr));
ผลลัพธ์
9
คำอธิบาย
Binary search peak: หาก mid < next -> peak ต้องอยู่ขวา (เพราะขึ้น) หาก mid < prev -> peak อยู่ซ้าย
Time: O(log n), Space: O(log n) เนื่องจาก recursion (สามารถทำ iterative ได้)
ขอบเขต: ใช้ -Infinity สำหรับ out-of-bounds
