用c语言实现：有一个已排好的数组，要求输入一个数后，按原来排序的规律讲它插入数组中

在C语言中，如果你想将一个已排序的数组按照特定规则插入一个新的数，你可以采用二分查找法找到合适的位置，然后将新数插入。以下是基本步骤：

1. 定义函数 `insert_sorted`，接受两个参数：已排序数组 `arr`、数组长度 `n` 和需要插入的新值 `key`。

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

int binary_search(int arr[], int n, int key) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key)
            return mid; // 如果找到相同的值，返回索引
        else if (arr[mid] < key)
            low = mid + 1; // 如果新值大于中间元素，更新左边界
        else
            high = mid - 1; // 如果新值小于中间元素，更新右边界
    }
    return low; // 如果没找到，返回插入位置（低界）
}

void insert_sorted(int arr[], int n, int key) {
    int pos = binary_search(arr, n, key);
    if (pos == n) {
        arr[n] = key; // 如果找不到插入点，就在末尾添加
    } else {
        memmove(&arr[pos+1], &arr[pos], sizeof(arr[0]) * (n - pos)); // 移动元素到右侧
        arr[pos] = key; // 插入新值
    }
}

2. 使用这个函数示例：

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 4; // 需要插入的数

    insert_sorted(arr, n, key);

    printf("Sorted array with inserted value: ");
    for (int i = 0; i <= n; ++i)
        printf("%d ", arr[i]);

    return 0;
}