用归并排序实现数组排序，用递归和分治实现数组元素查找c语言完整代码

下面是用归并排序实现数组排序的C语言代码：

#include <stdio.h>

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
    int size1 = mid - left + 1;
    int size2 = right - mid;
    int L[size1], R[size2];

    for (int i = 0; i < size1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < size2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < size1 && j < size2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < size1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < size2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序
void merge_sort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    int arr[] = {3, 5, 1, 9, 2, 7, 4, 6, 8};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    merge_sort(arr, 0, size - 1);

    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

下面是用递归和分治实现数组元素查找的C语言代码：

#include <stdio.h>

// 递归二分查找
int recursive_binary_search(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return recursive_binary_search(arr, mid + 1, right, target);
    } else {
        return recursive_binary_search(arr, left, mid - 1, target);
    }
}

// 分治二分查找
int divide_conquer_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 -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);

    int target = 5;

    printf("Recursive binary search:\n");
    int index1 = recursive_binary_search(arr, 0, size - 1, target);
    if (index1 == -1) {
        printf("The target %d is not found.\n", target);
    } else {
        printf("The target %d is found at index %d.\n", target, index1);
    }

    printf("\n");

    printf("Divide and conquer binary search:\n");
    int index2 = divide_conquer_binary_search(arr, size, target);
    if (index2 == -1) {
        printf("The target %d is not found.\n", target);
    } else {
        printf("The target %d is found at index %d.\n", target, index2);
    }

    return 0;
}