049. 实现二分查找算法

二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。它的基本思想是通过不断将数组分成两部分，逐步缩小查找范围，从而快速定位目标元素。二分查找的时间复杂度为 O(logn)，效率远高于线性查找。用C语言实现二分查找的代码，包括递归和非递归两种方式。

1. 递归实现二分查找

递归实现二分查找的核心是通过递归调用逐步缩小查找范围。

#include <stdio.h>

// 递归实现二分查找
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1; // 未找到目标值
    }

    int mid = left + (right - left) / 2; // 防止溢出

    if (arr[mid] == target) {
        return mid; // 找到目标值，返回索引
    } else if (arr[mid] > target) {
        return binarySearchRecursive(arr, left, mid - 1, target); // 在左半部分查找
    } else {
        return binarySearchRecursive(arr, mid + 1, right, target); // 在右半部分查找
    }
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target;

    printf("请输入要查找的数字：");
    scanf("%d", &target);

    int result = binarySearchRecursive(arr, 0, n - 1, target);

    if (result != -1) {
        printf("元素 %d 在数组中的索引为：%d\n", target, result);
    } else {
        printf("未找到元素 %d\n", target);
    }

    return 0;
}

2. 非递归实现二分查找

非递归实现二分查找的核心是通过循环逐步缩小查找范围。

#include <stdio.h>

// 非递归实现二分查找
int binarySearchIterative(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出

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

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

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target;

    printf("请输入要查找的数字：");
    scanf("%d", &target);

    int result = binarySearchIterative(arr, n, target);

    if (result != -1) {
        printf("元素 %d 在数组中的索引为：%d\n", target, result);
    } else {
        printf("未找到元素 %d\n", target);
    }

    return 0;
}

代码说明

递归实现：

递归函数 binarySearchRecursive 接收数组、左右边界和目标值作为参数。
每次计算中间索引 mid，并根据目标值与中间值的比较结果，递归调用左半部分或右半部分。
如果目标值等于中间值，返回中间索引。
如果左边界大于右边界，说明目标值不在数组中，返回 -1。

非递归实现：

使用循环逐步缩小查找范围。
每次计算中间索引 mid，并根据目标值与中间值的比较结果，更新左边界或右边界。
如果目标值等于中间值，返回中间索引。
如果循环结束仍未找到目标值，返回 -1。

示例运行

假设数组为：

int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

输入：

请输入要查找的数字：23

输出：

元素 23 在数组中的索引为：5

输入：

请输入要查找的数字：42

输出：

未找到元素 42

二分查找的特点

效率高：时间复杂度为 O(logn)，适合在大规模数据中查找。
适用条件：数组必须是有序的。
空间复杂度：递归实现的空间复杂度为 O(logn)，因为递归调用会占用系统栈空间。非递归实现的空间复杂度为 O(1)，因为只使用了少量额外变量。

二分查找是查找算法中的经典方法，适用于有序数组的快速查找。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)