如何在一个已经按升序排列的数组中，根据给定值的大小保持原有的排序顺序并插入新元素？用c语言写

在C语言中，要在已按升序排列的数组中根据给定值的大小保持原有排序顺序并插入新元素，可以采用二分查找法找到合适的位置，然后将新元素插入。以下是步骤：

1. **二分查找**：
- 定义一个`binary_search`函数，它接受数组、起始下标、结束下标和目标值作为参数。
- 使用二分查找算法确定目标值应该插入的位置`index`，确保数组在插入后仍然有序。

int binary_search(int arr[], int low, int high, int value) {
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == value)
            return mid;
        else if (arr[mid] > value)
            return binary_search(arr, low, mid - 1, value);
        else
            return binary_search(arr, mid + 1, high, value);
    }
    return low; // 如果未找到位置，返回低索引以便插入
}

2. **插入新元素**：
- 找到插入位置后，在`arr[index]`处插入新值`new_value`。

void insert_sorted(int arr[], int n, int new_value) {
    int index = binary_search(arr, 0, n - 1, new_value);
    memmove(&arr[index + 1], &arr[index], sizeof(int) * (n - index)); // 移动元素
    arr[index] = new_value; // 插入新值
    n++; // 更新数组长度
}

3. **示例完整代码**：
- 假设`arr[]`是一个已经排好序的整数数组，`n`是当前长度，`new_value`是要插入的新值。

#include <stdio.h>
#include <stdlib.h>

//... (上面的二分查找函数)

void insert_sorted(int arr[], int n, int new_value) {
    int index = binary_search(arr, 0, n - 1, new_value);
    arr[index] = new_value;
    n++;
}

int main() {
    int arr[] = {1, 3, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int new_value = 5;

    printf("Original array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    insert_sorted(arr, n, new_value);

    printf("\nArray after insertion: \n");
    for (int i = 0; i <= n; i++) {
        printf("%d ", arr[i]); // 注意这里加一，因为n也包含了新的元素
    }

    return 0;
}