利用分治法， 写一个二分检索的递归算法，并利用任何一种语言实现，同时进行时间 复杂性分析。C语言

分治法是一种解决问题的经典策略，它将大问题分解成规模较小、相互独立的子问题，再将子问题逐层解决，最终合并结果得到原问题的答案。对于二分查找（Binary Search），它是数组中查找特定元素的一种高效算法，适用于有序数据。其递归版本如下：

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    if (high >= low) {
        int mid = low + (high - low) / 2;

        // 如果目标值等于中间元素，返回中间索引
        if (arr[mid] == target)
            return mid;
        
        // 如果目标值小于中间元素，向左半部分搜索
        if (arr[mid] > target)
            return binarySearch(arr, low, mid - 1, target);
        
        // 否则，向右半部分搜索
        else
            return binarySearch(arr, mid + 1, high, target);
    }

    // 未找到，返回 -1 表示目标不在数组内
    return -1;
}

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

    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found in the array\n");

    return 0;
}

时间复杂性分析：
二分查找的时间复杂度是 O(log n)，这是因为每次比较都将搜索范围减半。所以无论数组多大，查找次数都不会超过 log base 2 of n 次。这是一种非常高效的查找算法。