C++ 实现数组二分查找算法

算法原理与适用场景

二分查找（Binary Search）的核心思想是“分而治之”。它要求操作对象必须是按从小到大排列的有序数组。算法通过不断取当前搜索区间的中间元素作为基准，将目标值与基准值进行比较：

• 若目标值小于基准值，则在左半区间继续查找；
• 若目标值大于基准值，则在右半区间继续查找；
• 若两者相等，则查找成功，返回对应索引。

每次比较都能将搜索范围减半，因此其时间复杂度为 $O(\log n)$，远优于线性查找的 $O(n)$。

核心代码实现

以下代码演示了基于 int 类型数组的二分查找实现。函数采用递归方式实现逻辑简化，适合学习和基础应用场景。

#include <iostream>
#include <cstdio>
using namespace std;

/*
  功能：实现数组的二分法查找
  注意：此算法只适合按从小到大排列的数组
  
  参数说明：
    a[] : 要搜索的有序数组
    len : 当前待搜索子数组的元素个数
    key : 要查找的关键字
    
  返回值：
    关键字在原始数组中的下标
    返回 -1 表示未在数组中找到关键字
*/
int binSearch(int a[], int len, int key)
{
  // 基础情况：空数组或无效长度
  if(len < 1)
    return -1;

  // 计算当前中间位置索引
  int i = len / 2;
  
  // 如果找到目标值，直接返回当前索引
  if(key == a[i])
    return i; 
  
  // 如果目标值大于中间元素，且在有效范围内
  else if((key > a[i]) && (len - i > 0))
  {
    // 递归在后半段数组中查找
    // 传入新数组起始地址偏移量，并更新剩余长度
    int ii = binSearch(a + i + 1, len - i - 1, key);
    
    // 如果在后半段找到了结果
    if(ii != -1)
      // 需要加上前半段的长度(i+1)，得到相对于原数组的真实下标
      return ii + i + 1; 
    else
      // 后半段未找到，返回失败标识
      return -1; 
  }
  // 如果目标值小于中间元素，且中间元素不是第一个（避免死递归）
  else if(key < a[i] && i > 0) 
    // 递归在前半段数组中查找
    return binSearch(a, i, key);
  
  // 其他所有情况（包括关键值等于中间值但被前面捕获，或无法继续细分）
  else
    return -1; // 未在数组中找到关键字
}

int main()
{
  // 预定义一个升序排列的测试数组
  int a[] = {2, 4, 5, 20, 24, 35, 66, 78, 98};
  int len = sizeof(a) / sizeof(int);
  int i, key = -1;

  // 循环读取用户输入进行测试
  while(1)
  {
    cin >> key;
    
    // 执行查找并输出结果
    i = binSearch(a, len, key);
    printf("%d\n", i);
    
    // 设置退出条件，当输入大于100时结束程序
    if(key > 100)
      break;
  }
  
  return 0;
}

代码逻辑解析

第1步：定义查找函数入口

函数 binSearch 接收三个参数：a[]（指针指向当前搜索起点）、len（当前搜索区间长度）、key（目标值）。这种设计允许递归调用时通过调整指针和长度来传递子区间，而不必创建新的副本数组。

第2步：确定中间点与终止条件

使用 i = len / 2 计算中间索引。首先检查 len < 1 处理空区间情况，这是防止栈溢出的最后一道防线。接着判断 key == a[i]，这是查找成功的直接标志。

第3步：处理不同大小关系的分支

大于情况（后半段查找）：当 key > a[i] 时，进入右半部分。递归调用时，数组指针前进至 a + i + 1，因为中间元素 a[i] 已经被排除。新长度需减去左半部分及中间元素，即 len - i - 1。若递归返回非 -1 的值 ii，必须将其加上 i + 1 以校正全局下标。

小于情况（前半段查找）：当 key < a[i] 且 i > 0 时，进入左半部分。此时数组指针不变，长度缩减为 i。

主程序测试流程

main 函数初始化了一个具体的升序数组，并通过 while(1) 无限循环等待标准输入。这便于连续测试多个关键字。输出直接使用 printf 打印返回的下标索引。程序设定 key > 100 为退出信号，可根据实际需求修改或移除限制。

注意事项与排错

• 数组有序性：二分查找的前提严格依赖数组排序。如果传入无序数组，结果将是不可预测的。
• 整型溢出风险：本示例使用简单除法 len / 2。在实际工程的大数组处理中，通常建议使用 (left + right) / 2 或位运算 (left + right) >> 1 以防止地址计算时的整型溢出，虽然对于小型 int 数组通常影响不大。
• 数据类型匹配：示例针对 int 类型。若用于浮点数或其他结构体，需相应调整比较逻辑。

简要总结

上述 C++ 二分查找代码清晰地展示了递归思维在搜索算法中的应用。通过正确维护子数组的指针偏移量和长度参数，实现了高效的空间利用率。以上就是 C++ 二分法在数组中查找关键字的详细实现内容，更多关于 C++ 基础算法的资料请关注本站其它相关文章！