C++ 二分查找三大函数完整易懂教程（全注释源码）

前置知识

C++ 标准库二分三大函数：

1. lower_bound：返回第一个 ≥ 目标值的迭代器
2. upper_bound：返回第一个 > 目标值的迭代器
3. binary_search：判断数组是否存在目标值，返回 bool 要求：数组必须升序有序

一、手写底层二分通用模板（基础版，逐行注释）

先自己实现二分逻辑，再对照标准库源码思路

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

// 1. 手写 lower_bound：找第一个 >= val 的位置
int my_lower_bound(vector<int>& arr, int val) {
    // 左边界：数组起始下标
    int left = 0;
    // 右边界：数组末尾下一位（左闭右开 [left, right) 和标准库统一）
    int right = arr.size();

    // 区间有效就循环
    while (left < right) {
        // 计算中间下标，避免 left+right 溢出，等价于 (left+right)/2
        int mid = left + (right - left) / 2;

        if (arr[mid] >= val) {
            // 当前中间值≥目标，答案一定在左半区，收缩右边界
            right = mid;
        } else {
            // 当前中间值<目标，答案在右半区，收缩左边界
            left = mid + 1;
        }
    }
    // left == right，就是第一个≥val的下标
    return left;
}

// 2. 手写 upper_bound：找第一个 > val 的位置
int my_upper_bound(vector<int>& arr, int val) {
    int left = 0;
    int right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] > val) {
            // 当前中间值>目标，答案在左半区
            right = mid;
        } else {
            // 当前中间值≤目标，答案在右半区
            left = mid + 1;
        }
    }
    return left;
}

// 3. 手写 binary_search：判断val是否存在
bool my_binary_search(vector<int>& arr, int val) {
    // 先用lower找第一个>=val的下标
    int pos = my_lower_bound(arr, val);
    // 条件1：pos不能越界；条件2：该位置值等于val，说明存在
    if (pos < arr.size() && arr[pos] == val) {
        return true;
    }
    return false;
}

int main() {
    // 有序升序数组
    vector<int> nums = {1, 3, 3, 3, 5, 7, 9};
    int target = 3;

    int l_pos = my_lower_bound(nums, target);
    int u_pos = my_upper_bound(nums, target);
    bool exist = my_binary_search(nums, target);

    cout << "第一个 >=3 的下标：" << l_pos << endl;    // 输出1
    cout << "第一个 >3 的下标：" << u_pos << endl;     // 输出4
    cout << "数字3是否存在：" << (exist ? "是" : "否") << endl;
    // [l_pos, u_pos) 区间就是所有等于3的元素
    cout << "等于3的元素个数：" << u_pos - l_pos << endl; // 3个
    return 0;
}

二、标准库泛型版实现（模仿 STL 源码，支持任意迭代器，逐行注释）

STL 的二分函数是模板，支持数组、vector、string 等所有有序容器，下面复刻 STL 原版逻辑

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

// ==================== 复刻 STL lower_bound 模板 ====================
// InputIterator：任意支持++、*的迭代器；T查找值；Comp比较函数
template<class InputIterator, class T>
InputIterator stl_lower_bound(InputIterator first, InputIterator last, const T& val) {
    // 区间长度
    auto len = last - first;
    // 循环：长度大于0继续二分
    while (len > 0) {
        // 折半，取一半长度
        auto half = len / 2;
        // 中间迭代器位置：起点+半长
        InputIterator mid = first;
        mid += half;

        if (*mid < val) {
            // 中间元素小于目标，目标只能在右半段
            // 左边界移到mid下一位
            first = mid + 1;
            // 新区间长度 = 总长度 - 半长 -1
            len = len - half - 1;
        } else {
            // 中间元素>=目标，答案在左半段，缩小长度
            len = half;
        }
    }
    // first == last，第一个>=val的迭代器
    return first;
}

// ==================== 复刻 STL upper_bound 模板 ====================
template<class InputIterator, class T>
InputIterator stl_upper_bound(InputIterator first, InputIterator last, const T& val) {
    auto len = last - first;
    while (len > 0) {
        auto half = len / 2;
        InputIterator mid = first;
        mid += half;

        if (*mid <= val) {
            // 中间元素<=目标，去右半段找更大的
            first = mid + 1;
            len = len - half - 1;
        } else {
            // 中间元素>目标，左半段缩小范围
            len = half;
        }
    }
    return first;
}

// ==================== 复刻 STL binary_search 模板 ====================
template<class InputIterator, class T>
bool stl_binary_search(InputIterator first, InputIterator last, const T& val) {
    // 调用lower_bound拿到首个>=val的迭代器
    InputIterator it = stl_lower_bound(first, last, val);
    // 迭代器不越界 且 迭代器指向的值等于目标，说明存在
    return (it != last) && (*it == val);
}

int main() {
    vector<int> arr = {2,4,6,6,6,8,10};
    int x = 6;

    auto it_low = stl_lower_bound(arr.begin(), arr.end(), x);
    auto it_up = stl_upper_bound(arr.begin(), arr.end(), x);
    bool has = stl_binary_search(arr.begin(), arr.end(), x);

    cout << "lower_bound下标：" << it_low - arr.begin() << endl;
    cout << "upper_bound下标：" << it_up - arr.begin() << endl;
    cout << "目标存在？" << has << endl;
    cout << "6的总个数：" << it_up - it_low << endl;
    return 0;
}

三、三大函数核心区别总结

数组：[1,3,3,3,5]，查找 3

1. lower_bound → 下标1（第一个≥3）
2. upper_bound → 下标4（第一个>3）
3. 区间 [low, up) 存放所有等于3的元素，个数 = up - low
4. binary_search 只是封装 lower_bound，判断是否存在

四、关键细节注释讲解（必看）

1. 左闭右开区间 [left, right) 右边界是数组长度，不是最后下标，越界时直接返回末尾，不用单独判断溢出。
2. mid = left + (right-left)/2 避免 (left+right)/2 两个大数相加溢出。
3. while 循环条件 left < right 区间只剩一个元素时循环结束，left就是答案，不用额外判断。
4. lower 和 upper 唯一区别：判断符号
   • lower：arr[mid] >= val 右移右边界
   • upper：arr[mid] > val 右移右边界

五、标准库原生调用示例（对比手写代码）

#include <iostream>
#include <vector>
#include <algorithm> // 标准库二分头文件
using namespace std;

int main() {
    vector<int> a = {1,2,4,4,7};
    int v = 4;

    auto low = lower_bound(a.begin(), a.end(), v);
    auto up = upper_bound(a.begin(), a.end(), v);
    bool exist = binary_search(a.begin(), a.end(), v);

    cout << low - a.begin() << endl; // 2
    cout << up - a.begin() << endl;  // 4
    cout << exist << endl;
    return 0;
}