searchListBinary函数无法对vector执行查找的问题排查求助

注意：二分查找的前置要求是传入的vector已经按照升序完成排序，未排序的序列无法使用二分查找得到正确结果

现有代码问题汇总 #

你提交的二分查找代码存在3处核心逻辑错误：

• mid值仅在循环外计算一次，循环内调整完first、last边界后没有重新计算mid，导致后续判断永远基于初始中间值，无法正常收缩搜索区间
• 区间逻辑不统一：当前while (first <= last)的判断对应左闭右闭搜索区间，但last初始赋值为arg.end()（尾后迭代器，不属于有效元素范围），会出现解引用越界的未定义行为
• 未处理空vector边界场景：如果传入的vector为空，first + (last - first) / 2实际是end()，后续解引用直接崩溃

修正方案 #

方案1：保持左闭右闭区间逻辑 #

vector<int>::iterator searchListBinary(vector<int>& arg, int target) {
    // 空vector直接返回end
    if (arg.empty()) {
        return arg.end();
    }
    vector<int>::iterator first = arg.begin();
    // 左闭右闭区间尾边界指向最后一个有效元素
    vector<int>::iterator last = arg.end() - 1;

    while (first <= last) {
        // 每次循环都重新计算mid
        vector<int>::iterator mid = first + (last - first) / 2;
        if (*mid == target) {
            return mid;
        } else if (target < *mid) {
            last = mid - 1;
        } else {
            first = mid + 1;
        }
    }
    return arg.end();
}

注意：该方案需要提前判断vector是否为空，避免arg.end() - 1越界

方案2：适配C++迭代器习惯的左闭右开区间实现（更推荐） #

vector<int>::iterator searchListBinary(vector<int>& arg, int target) {
    vector<int>::iterator first = arg.begin();
    // 左闭右开区间尾边界直接用end，无需减1
    vector<int>::iterator last = arg.end();

    // 区间非空就继续搜索
    while (first != last) {
        vector<int>::iterator mid = first + (last - first) / 2;
        if (*mid == target) {
            return mid;
        } else if (target < *mid) {
            last = mid;
        } else {
            first = mid + 1;
        }
    }
    return arg.end();
}

该方案天然适配空vector场景，无需额外做非空判断，也不会出现尾后迭代器解引用问题

线性查找实现（需求补充） #

vector<int>::iterator searchListLinear(vector<int>& arg, int target) {
    for (auto it = arg.begin(); it != arg.end(); ++it) {
        if (*it == target) {
            return it;
        }
    }
    return arg.end();
}

内容的提问来源于stack exchange，提问作者MH9283