Tìm phần tử lớn nhất trong mảng tăng rồi giảm trong C++

Cho mảng tăng dần rồi giảm dần (bitonic). Tìm phần tử lớn nhất (đỉnh). Ví dụ: [8,10,20,80,100,250,450,100,3,2,1] → 450.

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

Ví dụ

#include <iostream>
using namespace std;

int getMaxElement(int array[], int left, int right) {
    if (left == right) return array[left];
    if ((right == left + 1) && array[left] >= array[right]) return array[left];
    if ((right == left + 1) && array[left] < array[right]) 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);
    else
        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);
}

Kết quả

The maximum element is: 450