หาค่าสูงสุดในอาร์เรย์ที่เพิ่มแล้วลด (Bitonic Array) ใน C++

Bitonic Array คืออาร์เรย์ที่เพิ่มขึ้นมาก่อน แล้วค่อยลดลง หาค่าสูงสุด (Peak) ได้ใน O(log n) ด้วย Binary Search แบบปรับ

ตัวอย่าง: [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] → Peak = 450

เงื่อนไข Binary Search

1. ถ้า arr[mid] > arr[mid-1] และ arr[mid] > arr[mid+1] → Peak อยู่ที่ mid
2. ถ้า arr[mid] > arr[mid+1] แต่มากกว่า arr[mid-1] → Peak อยู่ด้านซ้าย
3. ถ้า arr[mid] < arr[mid+1] → Peak อยู่ด้านขวา

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

#include <iostream>
using namespace std;

int getMaxElement(int array[], int left, int right) {
    if (left == right)
        return array[left];

    if (right == left + 1) {
        if (array[left] >= array[right]) return array[left];
        else return array[right];
    }

    int mid = (left + right) / 2;

    if (array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
        return array[mid];

    if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
        return getMaxElement(array, left, mid - 1);

    return getMaxElement(array, mid + 1, right);
}

int main() {
    int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
    int n = sizeof(array) / sizeof(array[0]);
    cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
    return 0;
}

ผลลัพธ์

The maximum element is: 450

ความซับซ้อน

เวลา: O(log n), พื้นที่: O(log n) เนื่องจาก Recursion

Iterative Version (O(1) Space)

int findPeakIterative(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((mid == 0 || arr[mid] >= arr[mid-1]) && 
            (mid == n-1 || arr[mid] >= arr[mid+1]))
            return arr[mid];
        else if (mid > 0 && arr[mid-1] > arr[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}