用C++找出数组中一个既不是最大也不是最小的元素

在C++中，要找出数组中既不是最大值也不是最小值的元素，可以采用分而治之的思想，将数组分为两部分，然后分别找到每部分的最大值和最小值，再在这两个边界之外查找中间元素。下面是一个简单的示例，假设已知数组长度并有额外的空间存放临时变量：

#include <iostream>
using namespace std;

int findNonExtremal(int arr[], int left, int right) {
    if (left >= right) // 如果只有一个元素，那么它既是最大也是最小
        return -1; // 返回一个特殊的值表示没有这样的元素

    int mid = left + (right - left) / 2;
    int max_left = (arr[mid] > arr[left]) ? mid : left;
    int min_right = (arr[mid] < arr[right]) ? mid : right;

    for (int i = max_left + 1; i <= min_right - 1; i++) {
        if (arr[i] != arr[max_left] && arr[i] != arr[min_right])
            return i; // 找到符合条件的元素
    }

    // 如果所有中间元素都是极端值，返回下一个非极端元素
    return (max_left == right - 1) ? left : right;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = findNonExtremal(arr, 0, n - 1);
    if (result != -1)
        cout << "A non-extremal element is: " << arr[result];
    else
        cout << "No such element exists in the array.";
    return 0;
}

这个程序会返回数组中第一个既不是最大也不是最小的元素。如果找不到这样的元素，就会返回-1。