C语言实现二分搜索算法：详解及时间复杂度分析

二分搜索是一种高效的搜索算法，用于在有序数组中查找特定目标元素。其核心思想是利用分治策略，每次将搜索范围缩小一半，直到找到目标元素或搜索范围为空。

下面是使用C语言实现二分搜索算法的示例代码：

#include <stdio.h>

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, low, mid - 1, target); // 在左半部分继续搜索
    }
    else {
        return binarySearch(arr, mid + 1, high, target); // 在右半部分继续搜索
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 7;
    int size = sizeof(arr) / sizeof(arr[0]);
  
    int result = binarySearch(arr, 0, size - 1, target);
  
    if (result == -1) {
        printf("目标元素未找到\n");
    }
    else {
        printf("目标元素在索引 %d 处\n", result);
    }
  
    return 0;
}

代码解析:

binarySearch(int arr[], int low, int high, int target) 函数实现二分搜索算法。
- arr: 待搜索的有序数组
- low: 搜索范围的起始索引
- high: 搜索范围的结束索引
- target: 要查找的目标元素
首先，检查搜索范围是否有效 (low > high)，如果无效则返回 -1，表示未找到目标元素。
计算中间索引 mid，并比较 arr[mid] 与 target 的值：
- 若 arr[mid] == target，则找到目标元素，返回 mid。
- 若 arr[mid] > target，则目标元素可能存在于左半部分，递归调用 binarySearch 函数，搜索范围为 [low, mid - 1]。
- 若 arr[mid] < target，则目标元素可能存在于右半部分，递归调用 binarySearch 函数，搜索范围为 [mid + 1, high]。

算法时间复杂度分析:

最优时间复杂度: O(1)。当目标元素是数组的中间元素时，只需要一次比较即可找到目标元素。
最坏时间复杂度: O(log n)。在最坏情况下，每次搜索都将数组大小减半，直到找到目标元素或搜索范围为空。
平均时间复杂度: O(log n)。在平均情况下，每次搜索都将数组大小减半，因此平均需要进行 log n 次比较。
空间复杂度: O(1)。该算法只需要常量级的额外空间用于存储变量。

总结:

二分搜索是一种高效的搜索算法，其时间复杂度为O(log n)，适用于在有序数组中查找目标元素。