2)插入排序中，将第i个元素插入到前面0~i-1位置中时，可以使用二分查找方法确定插入位置。写程序，使用二分查找法实现插入排序。（使用c语言）

在插入排序中，确实可以利用二分查找法加速寻找插入位置。不过，由于插入排序本身就是一种稳定的排序算法，其主要特点是逐步构建有序序列，所以对于已经排好序的部分，插入操作通常是在固定位置进行的，无需每次都进行二分查找。但在某些极端情况下，例如输入数据基本有序，二分查找的确可以提高效率。以下是使用二分查找辅助的插入排序示例，但请注意这不是标准的插入排序，而是一种优化版：

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

// 二分查找辅助函数
int binarySearch(int arr[], int left, int right, int target) {
    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 insertionSortWithBinarySearch(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int index = binarySearch(arr, 0, i - 1, key);
        // 使用二分查找找到插入位置，然后将key插入到相应位置
        memmove(&arr[index + 1], &arr[index], (i - index) * sizeof(arr[0]));
        arr[index] = key;
    }
}

int main() {
    int arr[] = {9, 7, 5, 11, 12, 2, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSortWithBinarySearch(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    return 0;
}