二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数组。它的基本思想是通过不断将查找范围缩小一半来快速定位目标值。

二分查找的原理

1. 前提条件：

• 数组必须是有序的（升序或降序）。

2. 算法步骤：

• 初始化两个指针：low 指向数组的起始位置，high 指向数组的末尾位置。
• 计算中间位置 mid = (low + high) / 2。
• 比较中间元素与目标值：
• 如果中间元素等于目标值，返回中间位置。
• 如果中间元素小于目标值，说明目标值在右半部分，更新 low = mid + 1。
• 如果中间元素大于目标值，说明目标值在左半部分，更新 high = mid - 1。
• 重复上述步骤，直到 low > high，表示目标值不存在。

3. 时间复杂度：

• O(log?n)，其中 nn 是数组的长度。

C语言实现二分查找

以下是二分查找的C语言实现代码：

#include 

// 二分查找函数
int binarySearch(int arr[], int size, int target) {
    int low = 0;              // 查找范围的起始位置
    int high = size - 1;      // 查找范围的结束位置

    while (low <= high) {
        int mid = low + (high - low) / 2; // 计算中间位置

        if (arr[mid] == target) {
            return mid; // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            low = mid + 1; // 目标值在右半部分
        } else {
            high = mid - 1; // 目标值在左半部分
        }
    }

    return -1; // 未找到目标值
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, , , }; // 已排序的数组
    int size = sizeof(arr) / sizeof(arr[0]);  // 数组长度
    int target = 7;                          // 目标值

    int result = binarySearch(arr, size, target);

    if (result != -1) {
        printf("目标值 %d 在数组中的索引是：%d\n", target, result);
    } else {
        printf("目标值 %d 未找到！\n", target);
    }

    return 0;
}

代码说明

1. binarySearch 函数：

参数：

• arr[]：已排序的数组。
• size：数组的长度。
• target：要查找的目标值。

返回值：

• 如果找到目标值，返回其索引。
• 如果未找到，返回 -1。

2. 主函数：

• 定义一个已排序的数组 arr。
• 调用 binarySearch 函数查找目标值。
• 根据返回值输出结果。

示例运行

输入：

int arr[] = {1, 3, 5, 7, 9, , , };
int target = 7;

输出：

目标值 7 在数组中的索引是：3

输入：

int target = ;

输出：

目标值  未找到！

总结

• 二分查找是一种高效的查找算法，适用于已排序的数组。
• 时间复杂度为 O(log?n)，远优于线性查找的 O(n)。
• 实现时需要注意边界条件，例如 low 和 high 的更新。