如何将基于int的二分查找算法改为使用size_t？求最优方案

云上老周

2026-7-26

使用size_t改写二分查找算法的最优方案

原二分查找算法依赖int作为索引类型，用负索引表示查找失败，但int的范围有限，无法适配超大数组。改用标准无符号索引类型size_t时，直接替换会触发无符号类型溢出问题（比如m=0时r = m-1会变成SIZE_MAX，导致死循环），以下是针对性的修改思路与最优实现：

核心问题分析

无符号类型不存在负数，原算法中r = m - 1的逻辑在m=0时会溢出为SIZE_MAX，导致l <= r恒成立，循环无法终止。
原(l + r) / 2的中间值计算方式，在l和r接近size_t最大值时会溢出，得到错误的中间索引。
初始边界r = length - 1在length=0时会直接变成SIZE_MAX，引发非法内存访问风险。

最优修改方案

改用左闭右开区间[l, r)的逻辑，避免边界溢出，同时用安全方式计算中间索引：

初始r设为length而非length-1，空数组场景直接跳过循环
循环条件改为l < r，每次迭代缩小范围，最后检查剩余的唯一元素
用l + (r - l) / 2计算中间值，避免l + r的溢出风险
调整边界移动逻辑，永远不执行r = m - 1这类可能溢出的操作

完整实现代码

#include <stddef.h>

size_t binary_search(unsigned array[], size_t length, unsigned needle) {
    size_t l = 0;
    size_t r = length;

    while (l < r) {
        size_t m = l + (r - l) / 2;
        if (array[m] < needle) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    // 循环结束后l == r，检查该位置是否为目标值
    if (l < length && array[l] == needle) {
        return l;
    }
    return (size_t)-1; // 返回SIZE_MAX表示查找失败
}