运用c语言，使用减治思想实现插入排序以及折半查找

在C语言中，我们可以利用减治思想（也称为二分搜索法）来分别实现插入排序和折半查找。

**插入排序（Insertion Sort）**：
插入排序是一种简单的排序算法，它的工作原理类似于打扑克牌时的操作，每次从未排序的数据中取出一个元素，在已排序的部分找到合适的位置插入。以下是基本步骤：

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

        // 将比key大的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

在这个过程中，并没有直接使用到减治思想，但确实涉及到比较操作，类似二分查找的过程。

**折半查找（Binary Search）**：
折半查找是基于数组已经排好序的情况下的查找算法，每次将待查范围缩小一半。下面是基本实现：

int binary_search(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // 如果中间元素正好是我们要找的
        if (arr[mid] == x)
            return mid;

        // 如果中间元素大于目标值，那么目标值一定在左半部分
        else if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);

        // 否则，目标值一定在右半部分
        else
            return binary_search(arr, mid + 1, r, x);
    }

    // 如果元素不存在于数组中，则返回-1
    return -1;
}

这里就是典型的减治思想应用，每次都将搜索范围减半直到找到目标值或者确定其不存在。