C++ STL 二分查找三大函数中小学生易懂教程

前置说明

1. 三个函数：binary_search、lower_bound、upper_bound
2. 前提硬性要求：数组/容器必须提前从小到大排好序，二分才能生效
3. 头文件必须包含：#include <algorithm>
4. 统一使用数组+vector两种例子，注释直白，适合信息学入门

函数总作用区别

完整带注释可运行代码

#include <iostream>
#include <algorithm>   // STL二分函数都在这里
#include <vector>
using namespace std;

int main()
{
    // 有序数组（二分必须先有序！乱数组会出错）
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    // 计算数组元素个数
    int len = sizeof(arr) / sizeof(arr[0]);

    // 目标查找数字
    int target = 7;
    cout << "原始有序数组：";
    for(int i = 0; i < len; i++)
        cout << arr[i] << " ";
    cout << "\n查找目标数字：" << target << "\n\n";


    // ========== 1. binary_search 判断元素是否存在 ==========
    // 参数：起始地址，末尾下一个地址，要找的值
    bool have = binary_search(arr, arr + len, target);
    if(have)
        cout << "1.binary_search：数组中存在数字" << target << endl;
    else
        cout << "1.binary_search：数组中没有该数字" << endl;


    // ========== 2. lower_bound 第一个 >= target 的位置 ==========
    // 返回指针 it_low，指向符合条件的元素
    int* it_low = lower_bound(arr, arr + len, target);
    // 指针减数组首地址 = 下标
    int pos_low = it_low - arr;
    cout << "2.lower_bound：第一个≥" << target << " 的下标：" << pos_low 
         << "，对应数值：" << *it_low << endl;


    // ========== 3. upper_bound 第一个 > target 的位置 ==========
    int* it_up = upper_bound(arr, arr + len, target);
    int pos_up = it_up - arr;
    cout << "3.upper_bound：第一个>" << target << " 的下标：" << pos_up 
         << "，对应数值：" << *it_up << endl;


    // ===================== 拓展：vector 用法（竞赛常用）=====================
    cout << "\n===== vector 容器版本演示 =====" << endl;
    vector<int> v = {2,4,6,8,10,12,14};
    int x = 8;

    // binary_search vector
    bool exist = binary_search(v.begin(), v.end(), x);
    cout << "vector里是否有" << x << "：" << (exist ? "是" : "否") << endl;

    // lower_bound vector，返回迭代器
    auto l = lower_bound(v.begin(), v.end(), x);
    cout << "lower_bound下标：" << l - v.begin() << endl;

    // upper_bound vector
    auto r = upper_bound(v.begin(), v.end(), x);
    cout << "upper_bound下标：" << r - v.begin() << endl;

    // 小技巧：两个相减 = 数字x出现的总次数
    int cnt = r - l;
    cout << "数字" << x << "一共出现" << cnt << "次" << endl;

    return 0;
}

运行输出结果

原始有序数组：1 3 5 7 9 11 13 15 
查找目标数字：7

1.binary_search：数组中存在数字7
2.lower_bound：第一个≥7 的下标：3，对应数值：7
3.upper_bound：第一个>7 的下标：4，对应数值：9

===== vector 容器版本演示 =====
vector里是否有8：是
lower_bound下标：3
upper_bound下标：4
数字8一共出现1次

重点细节通俗讲解（中小学生版）

1. binary_search

• 只管有没有，找不到返回false，找到true
• 不能告诉你数字在第几格，只做判断

2. lower_bound 下限边界

找大于等于目标的第一个位置 例：数组 [2,4,4,4,6]，找4 lower_bound → 下标1（第一个4）

3. upper_bound 上限边界

找严格大于目标的第一个位置 同上数组找4，upper_bound → 下标4（数字6）

实用小技巧（考试常考）

统计某个数字在有序数组中出现多少次： 出现次数 = upper_bound结果 - lower_bound结果

关键提醒（易错点）

1. 数组必须升序排序，没排序二分函数全部失效
2. 数组传参：arr 开头，arr+长度 结尾（结尾是取不到的边界）
3. vector传参：v.begin() 开头，v.end() 结尾
4. 指针/迭代器减去首地址，才能得到下标数字