C++如何实现二分查找？binary_search函数用法详解与手写实现进阶指南

二分查找大概是所有算法里名气与翻车率最不成正比的一个。原理说出来三秒钟就懂：有序数组里取中间值，比目标大就往左找，比目标小就往右找，每次把搜索范围砍一半，时间复杂度O(log n)。但真到了手写的时候，死循环、差一位、查不到明明存在的值，这些问题几乎人人都踩过。这篇文章先把C++标准库里的binary_search、lower_bound、upper_bound讲清楚，再回到手写实现，把区间写法和边界条件彻底掰开揉碎。

一、标准库三剑客：binary_search、lower_bound、upper_bound

C++标准库在<algorithm>头文件中提供了三个与二分查找相关的函数，很多人只知道第一个，结果在需要拿到元素位置的时候就卡住了。这三个函数都要求目标区间已经按升序排好，如果是自定义类型，还需要提供对应的比较规则。

先看最基础的binary_search，它的函数签名是bool binary_search(first, last, value)，返回值只有一个布尔值，告诉你value存在不存在，但不告诉你它在哪。也就是说，如果你的需求只是判断"有没有"，用它最直接；如果想知道"在哪"，它就无能为力了。下面是一段基础用法示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9, 9, 11};

    // 只判断存在性，返回 bool
    bool found = std::binary_search(nums.begin(), nums.end(), 7);
    std::cout << (found ? "找到了" : "不存在") << std::endl;  // 找到了

    // 自定义比较函数的版本：查找满足条件的元素
    auto cmp = [](int a, int b) { return a < b; };
    found = std::binary_search(nums.begin(), nums.end(), 6, cmp);
    std::cout << (found ? "找到了" : "不存在") << std::endl;  // 不存在
    return 0;
}

真正强大的是lower_bound和upper_bound。lower_bound(first, last, value)返回第一个大于等于value的元素的迭代器；upper_bound返回第一个大于value的元素的迭代器。如果所有元素都比value小，两者都会返回last。这两个函数配合起来，还能算出某个值在数组中出现的次数：upper_bound(...) - lower_bound(...)。这个技巧在处理重复元素时特别常用，比线性扫描高效得多。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9, 9, 11};

    // 第一个 >= 9 的位置
    auto lb = std::lower_bound(nums.begin(), nums.end(), 9);
    // 第一个 > 9 的位置
    auto ub = std::upper_bound(nums.begin(), nums.end(), 9);

    std::cout << "第一个9的下标: " << (lb - nums.begin()) << std::endl;  // 4
    std::cout << "9出现了 " << (ub - lb) << " 次" << std::endl;      // 2

    // 查找目标值是否存在并拿到位置
    int target = 7;
    auto it = std::lower_bound(nums.begin(), nums.end(), target);
    if (it != nums.end() && *it == target) {
        std::cout << "7在下标 " << (it - nums.begin()) << std::endl;  // 3
    }
    return 0;
}

还有一点要提醒：这三个函数默认都假设区间是升序的。如果你的数组是降序排列，直接传默认比较会得到错误结果，必须自己传比较器，比如降序数组要传std::greater<int>()或者写一个a > b形式的lambda。这是实际工程里非常常见的坑，尤其是数据来自别人接口、排序方式不确定的时候。

二、手写二分查找：两种区间写法的边界细节

面试和刷题时通常不允许直接调库，必须手写。手写二分的核心矛盾在于区间定义和边界更新必须严格自洽，一旦两者不匹配就会出现死循环或者漏掉元素。常见的写法有两种：左闭右闭[left, right]和左闭右开[left, right)。

先看左闭右闭写法。区间是[left, right]，意味着left和right指向的位置都是有效候选，所以循环条件是left <= right，初始时right取n - 1。当中间值不等于目标时，中间位置可以被明确排除，因此更新时是left = mid + 1或者right = mid - 1。这套逻辑环环相扣，改动任何一处都会出错：

// 左闭右闭写法：查找 target 是否存在
int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;   // 闭区间 [left, right]
    while (left <= right) {                   // 区间非空的条件是 left <= right
        int mid = left + (right - left) / 2;  // 防止溢出，等价于 (left+right)/2
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;  // mid 已排除
        else right = mid - 1;                          // mid 已排除
    }
    return -1;  // 没找到
}

再看左闭右开写法，这是标准库内部采用的风格。区间是[left, right)，right指向的位置本身不是候选，所以初始right取n，循环条件变成left < right。更新时，往右缩是left = mid + 1，往左缩却只能写right = mid，因为mid仍然是潜在候选区间的开边界。两种写法没有优劣之分，但绝对不能混用：比如左闭右闭的初始化配上了left < right的循环条件，就是典型的死循环来源。

// 左闭右开写法：查找第一个 >= target 的下标（等价 lower_bound）
int lowerBound(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size();   // 右开，right 初始为 n
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid;  // mid 可能是答案，不能跳过
        else left = mid + 1;                    // mid 一定不是答案
    }
    return left;  // 循环结束时 left == right，即答案位置
}

有两个细节值得单独强调。第一，mid = (left + right) / 2在left和right都很大时会整型溢出，改成left + (right - left) / 2是必须养成的习惯，或者直接用std::midpoint（C++20起提供）。第二，死循环几乎都出在"缩不下去"上：当区间只剩两个元素时，如果某次更新写成了left = mid而mid恰好等于left，区间就永远不再缩小。遇到死循环，优先检查mid的计算方式和左右更新的方向是否匹配。

三、进阶变体与实战场景

掌握了基础写法后，真正的考验是各种变体题。这类题目的共同特征是：数组不是纯升序，或者要找的不是精确匹配而是某个边界条件。核心思路是一样的——想清楚每一次二分时，如何判断答案在mid的左边还是右边。

第一个经典变体是旋转有序数组，比如{4, 5, 6, 7, 0, 1, 2}。它的特点是：从任意位置切开，至少有一半是严格升序的。每次取mid后，先判断哪一半是有序的，再判断目标值是否落在有序的那一半里，从而决定保留哪一半。这个判断顺序不能乱，否则会漏情况：

// 旋转有序数组查找（数组中无重复元素）
int searchRotated(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        // 左半段 [left, mid] 是否有序
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid])
                right = mid - 1;        // target 在有序的左半段
            else
                left = mid + 1;
        } else {  // 右半段 (mid, right] 有序
            if (nums[mid] < target && target <= nums[right])
                left = mid + 1;         // target 在有序的右半段
            else
                right = mid - 1;
        }
    }
    return -1;
}

第二个常见场景是答案具有单调性的题目，比如"最小的满足条件的x"。这类问题表面上不是查找，但只要"x越大越容易满足条件"这种单调关系成立，就可以对答案空间二分。写法上就是把nums[mid] == target换成自定义的check(mid)函数，其余骨架完全不变。这个思路能把大量O(n)甚至O(n²)的问题降到O(n log n)以下，是二分最值得深入掌握的用法。

第三个细节是浮点数二分。求平方根、求方程近似解时，循环条件不再是下标比较，而是while (right - left > 1e-6)这种精度控制，区间更新直接写left = mid和right = mid，因为浮点mid永远不会被"排除"，只是不断逼近。也可以固定循环100次来保证精度，两种方式都可行。需要注意精度阈值要根据题目要求设定，太小会导致循环次数暴增甚至死循环，一般是要求精度再加两个数量级的安全余量。

// 浮点二分：求 x 的平方根（x >= 1）
double mySqrt(double x) {
    double left = 0, right = x;
    while (right - left > 1e-8) {      // 精度控制
        double mid = left + (right - left) / 2;
        if (mid * mid > x) right = mid;  // mid 偏大，往左缩
        else left = mid;                  // mid 偏小或正好，往右缩
    }
    return left;
}

总结一下记忆要点：标准库函数优先用lower_bound，因为它的语义最通用，能覆盖存在性判断、定位、计数三类需求；手写时选定一种区间写法后坚持到底，初始化、循环条件、更新语句三者必须对应；变体题不背模板，而是每次都想清楚"mid处满足条件与否，分别说明答案在哪一侧"。把这三条想透，二分查找基本就不会再出错了。

C++二分查找binary_search函数lower_bound修改时间：2026-09-07 15:46:58