C语言数有序数组插入

在C语言中，向已排序的数组插入一个新元素通常涉及到两种策略：二分查找法和直接插入法。

1. **二分查找法插入**：
如果数组是升序排列，你可以先使用二分查找确定新元素应该插入的位置。这个过程通过比较中间元素和目标值，持续调整搜索范围直到找到正确位置。然后将新元素插入到该位置，确保数组仍然有序。

int binary_search(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // 找到适当位置并返回
    return left;
}

void insert_sorted_array(int* arr, int size, int value) {
    int index = binary_search(arr, size, value);
    memmove(&arr[index+1], &arr[index], sizeof(int)*(size - index));
    arr[index] = value;
}

2. **直接插入法**：
如果数组规模小或者对性能要求不高，可以直接遍历整个数组，逐个比较，找到合适位置插入。

void insert_directly(int* arr, int size, int value) {
    for (int i = 0; i < size; i++) {
        if (arr[i] > value) {
            memmove(&arr[i+1], &arr[i], sizeof(int) * (i));
            arr[i] = value;
            break;
        }
    }
}