หา Local Minima ในอาร์เรย์ด้วย Binary Search ใน C++

Local Minima คือองค์ประกอบที่น้อยกว่าหรือเท่ากับเพื่อนบ้านทั้งสองข้าง (มุมมองมุมเดียวถ้าอยู่ขอบ)

ตัวอย่าง: [9, 6, 3, 14, 5, 7, 4] → Local minima: 3, 5, 4 (คืนค่าใดค่าหนึ่งก็ได้)

อัลกอริทึม (Binary Search แบบปรับ)

1. หาจุดกึ่งกลาง mid
2. ถ้า arr[mid] น้อยกว่าทั้งซ้ายและขวา → คืนค่า mid
3. ถ้า arr[mid] > arr[mid-1] → ค้นหาด้านซ้าย
4. ถ้า arr[mid] > arr[mid+1] → ค้นหาด้านขวา

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

#include <iostream>
using namespace std;

int localMinima(int arr[], int left, int right, int n) {
    int mid = left + (right - left) / 2;

    bool leftOk = (mid == 0) || (arr[mid-1] > arr[mid]);
    bool rightOk = (mid == n-1) || (arr[mid+1] > arr[mid]);

    if (leftOk && rightOk)
        return mid;
    else if (mid > 0 && arr[mid-1] < arr[mid])
        return localMinima(arr, left, mid - 1, n);
    else
        return localMinima(arr, mid + 1, right, n);
}

int findLocalMinima(int arr[], int n) {
    return localMinima(arr, 0, n-1, n);
}

int main() {
    int arr[] = {9, 6, 3, 14, 5, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
    return 0;
}

ผลลัพธ์

Local minima is: 3

ความซับซ้อน

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