设线性表的数据元素都为整数，存放在顺序表 S 中且递增有序。设计算法，将 x 插入 到顺序表 S 的适当位置上，以保持线性表的有序性。要求算法的时间复杂度为 O(n)，空间复 杂度为 O(1)。

为了在递增有序的顺序表S中插入元素x并保持有序，你可以采用二分查找法来找到插入的位置，这样可以保证时间复杂度为O(n)。具体步骤如下：

1. 初始化两个指针，`left`和`right`，分别指向顺序表的起始位置（索引0）和结束位置（最后一个元素的索引）。

2. 计算中间位置 `mid = (left + right) // 2`。

3. 比较`S[mid]`与`x`的大小关系：
- 如果`S[mid] < x`，说明x应该插入在`mid+1`的位置，更新`left = mid + 1`。
- 否则如果`S[mid] > x`，说明x应该插入在`mid`之前，更新`right = mid - 1`。
- 如果`S[mid] == x`，可以直接跳过这一轮比较，因为x已经存在，无需插入。

4. 当`left`大于等于`right`时，表示找到了合适的插入位置，即`S[left]`就是比x小的最后一个元素，所以将x插入到`S[left]`之后。

以下是伪代码示例：

def insert_sorted_sequence(S, x):
    left = 0
    right = len(S) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if S[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
            
    S.insert(left, x)