1、设顺序表L中的数据元素递增有序。试写一算法，将数据元素x插入到顺序表L的适当位置，以保持该表的有序性。

算法如下：

1. 定义变量i,j，其中i指向顺序表L的第一个元素，j指向顺序表L的最后一个元素。
2. 当i<=j时，执行下列操作：
a. 计算中间位置mid=(i+j)/2
b. 如果x等于L[mid]，则将x插入到L[mid]的后面，插入完成后结束算法。
c. 如果x小于L[mid]，则在L的左半部分继续查找，令j=mid-1。
d. 如果x大于L[mid]，则在L的右半部分继续查找，令i=mid+1。
3. 将x插入到L[i]的位置，插入完成后结束算法。

代码如下：

void insert(int L[], int len, int x) {
    int i = 0, j = len - 1;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (x == L[mid]) {
            i = mid + 1;
            break;
        } else if (x < L[mid]) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    for (int k = len; k > i; k--) {
        L[k] = L[k - 1];
    }
    L[i] = x;
}

该算法的时间复杂度为O(logn)，其中n为顺序表L的长度。

相关问题

设顺序表L中的数据元素递增有序。试写一算法，将数据元素x插入到顺序表L的适当位置，以保持该表的有序性。

算法如下：

1. 定义变量i为顺序表L的起始位置，j为顺序表L的结束位置，k为中间位置。

2. 如果顺序表L为空，则将数据元素x插入到L的第一个位置。

3. 如果顺序表L不为空，则循环执行以下步骤：

- 令k=(i+j)/2，即将顺序表L分成两半。

- 如果x==L[k]，则将数据元素x插入到L的第k个位置。

- 如果x<L[k]，则令j=k-1，即在L的前半部分寻找插入位置。

- 如果x>L[k]，则令i=k+1，即在L的后半部分寻找插入位置。

4. 如果找不到插入位置，则将数据元素x插入到L的最后一个位置。

算法的时间复杂度为O(logn)，其中n为顺序表L的长度。

1、设顺序表L中的数据元素递增有序。试写一算法，将数据元素x插入到顺序表L的适当位置，以保持该表的有序性。 c语言写

算法如下：

void insert(int L[], int len, int x) {
    int i = 0, j = len - 1;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (x == L[mid]) {
            i = mid + 1;
            break;
        } else if (x < L[mid]) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    for (int k = len; k > i; k--) {
        L[k] = L[k - 1];
    }
    L[i] = x;
}

该算法的时间复杂度为O(logn)，其中n为顺序表L的长度。