设计算法找出数组 a[n]中一个既不是最大也不是最小的元素,并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述

确定数组 `a[n]` 中既不是最大值也不是最小值的元素，可以采用“中间值查找”算法，也称为“三分查找”。这种算法假设数组已经排好序，通过将数组分为三部分，每次都排除掉一部分不可能包含目标值的范围，直到找到中间元素，它就可能是我们要找的元素。

**伪代码**:

function findMiddleElement(a[], low, high):
    if low <= high:
        mid = (low + high) // 2   // 计算中间索引
        if a[mid] < a[high]:      // 如果中间元素小于最高，目标在右半部分
            return findMiddleElement(a, mid+1, high)
        elif a[mid] > a[low]:     // 如果中间元素大于最低，目标在左半部分
            return findMiddleElement(a, low, mid-1)
        else:                     // 否则，中间元素就是我们要找的
            return a[mid]
    return None                  // 搜索完毕，未找到符合条件的元素

array = [排序后的数组a[n]]
result = findMiddleElement(array, 0, n-1)

**C++ 描述**:

#include <vector>
using namespace std;

int findMiddleElement(vector<int>& arr, int low, int high) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < arr[high])
            return findMiddleElement(arr, mid + 1, high);
        else if (arr[mid] > arr[low])
            return findMiddleElement(arr, low, mid - 1);
        else
            return arr[mid];
    }
    return -1; // 表示没有找到符合条件的元素
}

// 示例用法:
vector<int> array = {已排序的整数列表};
int middleElement = findMiddleElement(array, 0, array.size() - 1);

**最坏情况下的比较次数**：
在这种情况下，最坏的情况发生在数组本身就是有序的，并且中间元素恰好是最小或最大的时候。每次查找都会排除一半的可能性，所以最坏需要进行 log2(n) 次比较，其中 n 是数组长度。因为最后一次比较会直接返回结果，所以总比较次数为 log2(n) - 1。