C语言二分查找算法详解与代码实现

二分查找的基本原理

二分查找，又称折半查找，是一种在有序序列中查找特定元素的算法。相较于线性查找逐个遍历的方式，二分查找通过“分治”策略大幅提升了查找效率。

其基本思想如下：

1. 确定边界：定义查找范围的左边界（low）和右边界（high）。
2. 取中间值：计算中间位置 mid = (low + high) / 2，并获取该位置的值。
3. 比较判断：

• 若中间值等于目标值，则查找成功，返回索引。
• 若中间值大于目标值，说明目标值可能在左半部分，调整右边界 high = mid - 1。
• 若中间值小于目标值，说明目标值可能在右半部分，调整左边界 low = mid + 1。

注意：使用二分查找的前提是数据必须是有序的（升序或降序）。如果数据无序，需先进行排序操作。

C语言代码实现

以下是基于标准C语言的二分查找函数实现。该函数接收一个整型数组、数组长度以及待查找的目标值，返回目标值在数组中的索引，若未找到则返回 -1。

#include <stdio.h>

// 二分查找函数
// a[]: 有序数组
// n: 数组长度
// key: 要查找的目标值
int binarySearch(int a[], int n, int key) {
    int low = 0;          // 左边界初始化
    int high = n - 1;     // 右边界初始化
    
    while (low <= high) {
        // 计算中间位置，防止溢出可写作: low + (high - low) / 2
        int mid = (low + high) / 2;
        int midVal = a[mid];
        
        if (midVal < key) {
            // 目标值在右半部分
            low = mid + 1;
        } else if (midVal > key) {
            // 目标值在左半部分
            high = mid - 1;
        } else {
            // 找到目标值，返回索引
            return mid;
        }
    }
    
    // 未找到目标值
    return -1;
}

int main() {
    int i, val, ret;
    // 定义一个已排序的数组
    int a[8] = {-32, 12, 16, 24, 36, 45, 59, 98};
    
    // 打印数组内容
    for(i=0; i<8; i++)
        printf("%d\t", a[i]);
    printf("\n请输入所要查找的元素：");
    
    // 读取用户输入
    scanf("%d", &val);
    
    // 调用二分查找函数
    ret = binarySearch(a, 8, val);
    
    // 根据返回值判断查找结果
    if (-1 == ret)
        printf("查找失败 \n");
    else
        printf("查找成功 \n");
        
    return 0;
}

算法执行过程图解

为了更直观地理解二分查找的工作机制，我们可以观察其在具体数据集中的执行流程。假设我们要在数组 {-32, 12, 16, 24, 36, 45, 59, 98} 中查找元素 12。

如上图所示的执行过程：

1. 第一轮查找：初始 low=0, high=7。中间位置 mid=(0+7)/2=3，对应值为 24。因为 12 < 24，所以目标值位于左半部分，更新 high = mid - 1 = 2。
2. 第二轮查找：此时 low=0, high=2。中间位置 mid=(0+2)/2=1，对应值为 12。因为 12 == 12，查找成功，返回索引 1。

在 main 函数中，通过检查 binarySearch 函数的返回值来判断是否查找到目标。若返回值为 -1，则表示查找失败；否则表示查找成功，并可进一步利用返回的索引访问该元素。

关键参数与注意事项

在实际开发中使用二分查找时，需注意以下几点：

• 数组有序性：务必确保传入的数组是单调递增或递减的。如果数组无序，直接应用此算法将无法得到正确结果。
• 边界条件：循环条件为 low <= high，这是为了保证当查找区间缩小到只剩一个元素时仍能进行检查。如果使用 low < high，可能会漏掉最后一个元素。
• 整数溢出风险：在极大规模数据中，(low + high) / 2 可能导致整数溢出。建议改为 low + (high - low) / 2 或使用位运算 (low + high) >> 1。

总结

二分查找是利用数据有序特性提升搜索效率的经典算法。通过不断折半缩小搜索空间，它能在 O(log n) 的时间复杂度内完成查找任务。掌握其C语言实现有助于深入理解基础数据结构与算法逻辑。以上就是对二分查找法在C语言中应用的详细介绍，更多关于编程算法的资料请关注本站其它相关文章！