โปรแกรม C++ หา Peak Element ในอาร์เรย์ด้วยวิธี Binary Search

ภาพรวม

โปรแกรม C++ นี้สาธิตการหา Peak Element (องค์ประกอบที่มีค่ามากกว่าหรือเท่ากับเพื่อนบนทั้งสองข้าง) ในอาร์เรย์โดยใช้วิธี Binary Search ซึ่งมีความซับซ้อนด้านเวลา O(log n) อัลกอริธึมจะคืนค่า Peak แรกที่พบ

อัลกอริธึม

1. ฟังก์ชัน PeakElement() รับพารามิเตอร์: อาร์เรย์ arr, ดัชนีเริ่มต้น start, และดัชนีสิ้นสุด end
2. คำนวณดัชนีกลาง mid = (start + end + 1) / 2
3. ตรวจสอบเงื่อนไข:
   • ถ้า mid อยู่ขอบเขตและค่าที่ mid มากกว่าเพื่อนบน → คืนค่า mid
   • ถ้าค่าที่ mid มากกว่าเพื่อนบนทั้งสองข้าง → คืนค่า mid
   • ถ้าค่าข้างขวา (mid+1) มากกว่า → เรียกฟังก์ชันซ้ำกับส่วนขวา
   • ถ้าค่าข้างซ้าย (mid-1) มากกว่า → เรียกฟังก์ชันซ้ำกับส่วนซ้าย

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

int PeakElement(int a[], int start, int end) {
    int mid = (end + start + 1) / 2;
    
    // ตรวจสอบขอบเขต
    if ((a[mid] > a[mid+1] && mid == start) || (a[mid] > a[mid-1] && mid == end)) {
        return a[mid];
    }
    // Peak อยู่ตรงกลาง
    else if (a[mid] > a[mid-1] && a[mid] > a[mid+1]) {
        return a[mid];
    }
    // ไปทางขวา
    else if (a[mid] <= a[mid+1]) {
        return PeakElement(a, mid+1, end);
    }
    // ไปทางซ้าย
    else {
        return PeakElement(a, start, mid-1);
    }
}

int main() {
    int n;
    cout << "Enter the number of data element: ";
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cout << "Enter element " << i+1 << ": ";
        cin >> arr[i];
    }
    int peak = PeakElement(arr, 0, n-1);
    cout << "\nThe peak element of the given array is: " << peak;
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the number of data element: 5
Enter element 1: 45
Enter element 2: 26
Enter element 3: 70
Enter element 4: 60
Enter element 5: 15
The peak element of the given array is: 70

คำอธิบายเพิ่มเติม

Peak Element หมายถึงองค์ประกอบที่มีค่ามากกว่าหรือเท่ากับองค์ประกอบที่อยู่ติดกันทั้งสองข้าง (สำหรับองค์ประกอบขอบเขต ต้องมากกว่าเพื่อนบนเพียงข้างเดียว) วิธี Binary Search ช่วยลดความซับซ้อนจาก O(n) เป็น O(log n) โดยการตัดครึ่งพื้นที่ค้นหาในแต่ละขั้นตอน