线性结构 二分查找递归实现和排序 c语言代码

二分查找是一种高效的查找算法，其基本思想是在有序数组中查找某个元素时，每次取中间位置的值进行比较，如果该值大于目标元素，则在左半部分继续查找，否则在右半部分查找，直到查找到目标元素或者数组中不存在该元素为止。以下是二分查找的递归实现和排序的C语言代码示例：

// 二分查找递归实现
int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, mid+1, high, target);
    } else {
        return binarySearch(arr, low, mid-1, target);
    }
}

// 快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot-1);
        quickSort(arr, pivot+1, high);
    }
}

// 快速排序辅助函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return i+1;
}

在上述代码中，我们首先定义了一个二分查找的递归实现函数 binarySearch()，其中 arr[] 表示有序数组，low 和 high 分别表示数组的起始和结束位置，target 表示要查找的目标元素。在函数中，我们先计算出数组的中间位置 mid，如果中间位置的值等于目标元素，则直接返回 mid，否则根据中间位置的值和目标元素的大小关系来决定在左半部分还是右半部分进行查找。如果数组中不存在目标元素，则返回 -1。

接下来，我们定义了一个快速排序的函数 quickSort()，其中 low 和 high 分别表示数组的起始和结束位置。在函数中，我们先通过 partition() 函数将数组分为两部分，然后对左半部分和右半部分分别进行递归排序。partition() 函数用于将数组分为两部分，其中 pivot 表示基准元素，i 表示分界点，j 表示当前遍历到的位置。在遍历过程中，如果当前位置的值小于基准元素，则将其移动到分界点的左边。最终，将基准元素移动到分界点，并返回分界点的位置。