C/C++二分查找算法：从原理到测试的完整实现指南

核心原理与溢出风险

二分查找通过不断缩小搜索范围来定位目标元素。其基本思想是：开始时范围为整个数组，每次比较中间元素与目标值，丢弃一半不可能包含目标的范围，直到找到目标或范围为空。尽管该算法逻辑简单，但在实际实现中常因边界处理不当或整数运算溢出而引入Bug。

最常见的错误在于中间下标的计算。若直接使用 (low+high)/2，当索引值过大导致 low+high 超过整型上限时，会发生整型溢出，进而引发内存访问越界。正确的做法是使用减法代替加法：

m = low + ((high - low) >> 1)

迭代实现：非对称区间法

采用左闭右开 [left, right) 的非对称区间定义通常更简洁，且能避免空指针问题。该方法的核心逻辑如下：

1. 初始化：设置左边界 l=0，右边界 u=n（即数组长度）。
2. 循环条件：当 l < u 时持续执行。
3. 更新策略：
   • 若目标值小于中间值 a[m]，则目标在左半部分，更新 u = m。
   • 若等于中间值，返回索引 m。
   • 若大于中间值，则目标在右半部分，更新 l = m + 1。

int binarysearch_non_symmetric(int a[], int n, int x)
{
    int l = 0, u = n; // 左闭右开 [0, n)
    while(l < u)
    {
        int m = l + ((u - l) >> 1);
        if(x < a[m])
            u = m;
        else if(x == a[m])
            return m;
        else
            l = m + 1;
    }
    return -1; // 未找到
}

纯指针形式的优势

在将上述算法转换为纯指针操作时，非对称区间具有明显优势。如果使用传统的对称区间 [left, right]，当数组为空（长度为0）时，计算中间指针可能会指向无效地址（如 start - 1）。而在非对称区间实现中，起始状态即为合法的空集判断，无需额外校验空指针。

int binarysearch_ptr(int *a, int n, int x)
{
    int *l = a; 
    int *u = a + n; // 右边界指向末尾之后的位置
    while(l < u)
    {
        int *m = l + ((u - l) >> 1);
        if(x < *m)
            u = m;
        else if(x == *m)
            return (int)(m - a);
        else
            l = m + 1;
    }
    return -1;
}

递归实现与其他变体

除了迭代，二分查找也可用递归实现。递归版本需注意参数的传递顺序和终止条件的设定。

int binarysearch_recursive(int a[], int left, int right, int x)
{
    if(left > right)
        return -1;
    
    int m = left + ((right - left) >> 1);
    if(x < a[m])
        return binarysearch_recursive(a, left, m - 1, x);
    else if(x == a[m])
        return m;
    else
        return binarysearch_recursive(a, m + 1, right, x);
}

查找首次出现的位置

标准二分查找在数组存在重复元素时，返回的是其中任意一个匹配项的索引。若需定位重复元素的第一次出现位置，需在匹配成功后继续向左收缩右边界，并记录当前找到的索引。

另一种更为优雅的解法源自《编程珠玑》，利用两个边界分别标记“小于目标值的最后一个位置”和“大于等于目标值的最前一个位置”。

int find_first_occurrence(int a[], int n, int x)
{
    int l = -1; 
    int u = n;
    while(l + 1 < u)
    {
        int m = l + ((u - l) >> 1);
        if(a[m] < x)
            l = m;
        else
            u = m;
    }
    // 检查 u 是否越界或其指向的值是否确实等于 x
    return (u >= n || a[u] != x) ? -1 : u;
}

构建健壮的测试用例

正如《代码之美》所强调的，二分查找的正确性高度依赖于严格的测试。以下提供了基于 assert 的测试框架，覆盖冒烟测试、边界测试及自动化随机测试。

关键测试维度

• 中值计算测试：单独测试 mid 计算函数，特别是涉及极大数值（如 INT_MAX）时的行为，确保不溢出。
• 冒烟测试：对正常数据进行基本的成功与失败查找。
• 边界测试：
  • 空数组（n=0）。
  • 单元素数组。
  • 首元素、尾元素。
  • 最小值（负数）、最大值及零。
• 自动化遍历测试：生成有序数组（如 i*10），遍历所有元素进行查找，确保每个都能命中。
• 随机数据测试：生成随机无序数组后排序，再对特定序列进行查找，验证整体逻辑的一致性。

#include <iostream>
#include <cassert>
#include <algorithm>
#include <ctime>
using namespace std;

// 模拟计算中值，用于独立测试
int calmid(int l, int u) { return l + ((u - l) >> 1); }

int main() 
{
    long start, end;
    start = clock();

    // 1. 中值计算专项测试
    assert(calmid(0, 1) == 0);
    assert(calmid(0, 2) == 1);
    assert(calmid(1000000, 2000000) == 1500000);
    // 极值测试防止溢出
    assert(calmid(2147483646, 2147483647) == 2147483646);
    
    // 2. 基础功能测试
    int a[9] = {-2147483648, -13, -10, -5, -3, 0, 1, 400, 2147483647};
    assert(binarysearch_non_symmetric(a, 9, 0) == 5);
    assert(binarysearch_non_symmetric(a, 9, 2147483647) == 8);
    
    // 3. 边界条件测试
    assert(binarysearch_non_symmetric(a, 0, 1) == -1);       // 空数组
    assert(binarysearch_non_symmetric(a, 1, -2147483648) == 0); // 仅首个元素
    assert(binarysearch_non_symmetric(a, 9, -2147483647) == -1); // 超出范围的最小值

    // 4. 自动化测试：连续数据
    int b[10000]; 
    for(int i = 0; i < 10000; i++) 
    {
        b[i] = i * 10;
        for(int j = 0; j <= i; j++) 
        {
            assert(binarysearch_non_symmetric(b, i + 1, j * 10) == j);
        }
    }
    
    // 5. 自动化测试：随机数据
    srand((unsigned)time(NULL));
    for(int i = 0; i < 10000; i++) 
    {
        for(int k = 0; k <= i; k++)
             b[k] = rand() % 1000000;
        sort(b, b + i + 1);
        
        int target = b[i / 2]; // 测试中间元素
        int res = binarysearch_non_symmetric(b, i + 1, target);
        assert(res != -1 && b[res] == target);
    }

    end = clock();
    cout << "All tests passed. Time: " << (end - start) / 1000.0 << "s" << endl;
    return 0;
}

总结而言，编写安全的二分查找不仅要关注核心逻辑，还需妥善处理边界收敛与潜在的资源越界风险。建议在实际开发中，始终采用非对称区间或防御性编程习惯，并结合全面的自动化测试套件以确保可靠性。

以上就是二分查找算法在C/C++中的详细应用与测试内容，更多关于C++算法优化的资料请关注本站其它相关文章！