分治算法2 请按照分治思想编写以下代码： （1 芯片测试 (2）快速排序 c语言

分治算法是一种将复杂的问题分解成更小的相似问题来解决的技术，通常分为三个步骤：分解、求解和合并。其中，芯片测试（也称为二分查找）和快速排序都是经典的分治算法实例。

1. **二分查找（芯片测试）** - 这是一种在有序数组中查找特定元素的高效算法。以下是C语言的一个简单版本：

int binarySearch(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 binarySearch(arr, l, mid - 1, x);
        
        // 否则，它一定在右半部分
        else
            return binarySearch(arr, mid + 1, r, x);
    }
    
    // 如果没有找到元素，返回 -1
    return -1;
}

2. **快速排序（Quick Sort）** - 一种常用的排序算法，通过选择一个基准值并将数组分成两部分，一部分的所有元素都比基准值小，另一部分所有元素都比基准值大，然后递归地对这两部分进行同样的操作。下面是一个简单的C语言版快速排序示例：

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; 
    int i = (low - 1); 

    for (int j = low; j <= high- 1; j++) {
        if (arr[j] < pivot) {
            i++; 
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 使用快速排序函数
void quickSortExample(int arr[], int n) {
    quickSort(arr, 0, n - 1);
}