Tìm cực tiểu cục bộ trong mảng trong C++

Cho mảng A n phần tử. Phần tử A[x] là cực tiểu cục bộ nếu nó ≤ cả hai láng giềng (phần tử đầu/cuối chỉ cần ≤ láng giềng duy nhất). Nếu nhiều cực tiểu, trả về một trong số chúng. Ví dụ: [9,6,3,14,5,7,4] → cực tiểu có thể là 3, 5, 4.

Dùng tìm kiếm nhị phân: Nếu mid < cả hai láng giềng → trả về mid. Nếu mid > trái → tìm bên trái. Nếu mid > phải → tìm bên phải.

Ví dụ

#include <iostream>
using namespace std;

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

Kết quả

Local minima is: 3