c++数组中，五个已经排好顺序的数，在输入一个数重新排序

在C++中，如果你有一个已排序的数组，并需要通过插入一个新元素重新排序，可以采用“二分查找”和“插入排序”的方法。这里是一个基本步骤：

1. **二分查找**：首先，你需要找到新元素应该插入的位置。将待插入的值与数组中间元素比较，如果新值小于中间元素，则在左半部分继续查找；反之，如果大于，则在右半部分查找。这个过程会一直持续到找到合适的插入位置，使得插入后仍然保持升序排列。

2. **插入操作**：找到插入位置后，将新元素移动到该位置，同时确保左侧元素都比它大，右侧元素都比它小。

以下是一个简单的示例代码片段：

#include <iostream>
using namespace std;

void binarySearch(int arr[], int target, int left, int right) {
    if (left > right)
        return;

    int mid = (left + right) / 2;
    if (arr[mid] == target)
        return; // 找到了目标值，不需要插入

    else if (arr[mid] > target)
        binarySearch(arr, target, left, mid - 1); // 新值应在左半部分

    else
        binarySearch(arr, target, mid + 1, right); // 新值应在右半部分
}

void insertSort(int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) { // 插入前移较大的元素
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 将新元素放在正确位置
    }
}

void rearrangeAfterInsertion(int arr[], int n, int num) {
    binarySearch(arr, num, 0, n - 1);
    insertSort(arr, n); // 由于可能有多个相同的num，再做一次插入排序
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num = 4;

    rearrangeAfterInsertion(arr, n, num);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
    
    // 相关问题--