2. 假设有一个非空顺序表L，其中的元素非递减有序排列，请设计一个算法在插入元素x后保持该顺序表仍然非递减有序排列，假设插入操作肯定成功，插入成功后返回插入元素所在位置。用c++写出来

为了在一个已排序的非空顺序表L（例如一个整数数组）中插入元素x并保持非递减有序，可以采用二分查找法找到合适的位置，然后将x插入到该位置。以下是C++实现的一个简单版本：

#include <iostream>

// 假设列表元素是一个模板类型T，且实现了比较运算符<
template <typename T>
size_t insertAndKeepSorted(T* L, size_t n, const T& x) {
    // 如果列表为空，直接插入第一个位置
    if (n == 0)
        return 0;

    // 使用二分查找找到正确位置
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (L[mid] > x) {
            high = mid - 1;  // x应位于mid左侧
        } else {
            low = mid + 1;   // x应位于mid右侧
        }
    }

    // 插入x，并更新大小
    L[low] = x;
    return low;
}

int main() {
    // 示例用法
    int L[] = {1, 3, 5, 7};
    size_t n = sizeof(L) / sizeof(L[0]);
    int x = 4;
    size_t position = insertAndKeepSorted(L, n, x);
    std::cout << "Inserted " << x << " at position " << position << std::endl;

    return 0;
}

这个函数首先检查列表是否为空，如果是则插入在第一位。然后使用二分查找确定`x`应该插入的位置，如果某个中间值大于`x`，说明`x`应在该值的左边，反之则在右边。最后，将`x`插入到找到的位置并返回。