企业官网建设流程全解析

1. 从一道题说起：二分查找到底在解决什么

如果你刷过算法题、写过搜索引擎、或者单纯想在一亿个有序号码里快速找一个人，大概率绕不开二分查找。这个算法的名字你可能在 C++ 入门的第三天就听过，但真到面试、比赛或者生产环境里，很多人手写出来的版本要么死循环，要么越界，要么结果差一位。问题从来不是“二分查找难”，而是你对它的区间定义、边界收缩、退出条件理解得不够扎实。

二分查找的适用条件非常简单：一组数据必须有序（或者具备单调性），并且支持随机访问。它做的事情本质上是不断把“可能存在的范围”砍半，每次通过比较中间值和目标值，排除掉一半的数据，从而把查找时间从 O(n) 降到 O(log n)。举个例子，如果有一百万个有序整数，顺序查找最坏要比较一百万次，而二分查找最多只需要比较 20 次。这个差距在数据量大的时候是降维打击，这也是为什么数据库索引、操作系统调度、游戏热更新校验等场景里，二分思想无处不在。

这篇博文不会只给你贴一份能跑的代码，而是把 C++ 里写二分查找时最容易出错的细节、各种变体写法、STL 标准库的现成工具，以及我在实际项目中踩过的坑都摊开来讲。适合刚入门 C++ 的算法新手，也适合已经刷了不少题但总被边界条件折磨的人。读完你不仅能写对“找一个数”的二分，还能熟练处理“找左边界”“找右边界”“浮点数二分”“二分答案”这些进阶场景。

2. 手写二分：三个版本的正确姿势

2.1 最经典的迭代写法

先看最标准的“在有序数组中查找一个给定值”的写法，我用左闭右闭区间[left, right]来定义搜索范围。这种定义方式最直观，也最容易推导。

#include <vector> int binarySearch(const std::vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; // [left, right] 闭区间 while (left <= right) { int mid = left + (right - left) / 2; // 避免 left + right 溢出 if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; // target 在右半部分 } else { right = mid - 1; // target 在左半部分 } } return -1; // 未找到 }

这里有几个关键决策点。第一，循环条件为什么是left <= right？因为当left == right时，当前区间内还有一个元素没有检查过，必须再进入一次循环判断这个元素是否等于目标值。如果你写成left < right，最终会漏掉这个元素，除非你在循环结束后再单独补一次判断。第二，当nums[mid] < target时，说明 mid 位置的值已经比目标值小了，所以目标值不可能在mid位置，下一轮左边界可以直接设为mid + 1；同理，目标值小于mid位置的值时，右边界设为mid - 1。每一次循环都能严格收缩区间，所以循环一定会终止。

第三，也是很多人容易忽略的，mid的计算为什么要写成left + (right - left) / 2而不是(left + right) / 2？原因是在极端情况下，比如数组长度为INT_MAX级别，left + right可能会超过 int 能表示的范围，发生整型溢出。虽然实际刷题中很少遇到这么大的数组，但这是个好习惯。如果right - left出现负数，说明你这个区间定义已经错了，需要回头检查收缩逻辑。

2.2 递归版本的写法与栈开销

很多教材喜欢展示递归版本的二分，因为它更贴近“分治”思想。代码确实简洁：

int binarySearchRecursive(const std::vector<int>& nums, int target, int left, int right) { if (left > right) { return -1; } int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { return binarySearchRecursive(nums, target, mid + 1, right); } else { return binarySearchRecursive(nums, target, left, mid - 1); } }

递归版本和迭代版本逻辑完全等价，终止条件就是区间为空，即left > right。递归的最大问题是栈空间。因为二分查找每次只递归一侧，深度是 O(log n)，对于一亿个元素来说深度大约 27 层，通常不会爆栈。但如果是在某些嵌入式环境或者递归深度受限的平台上，迭代版本会更稳妥。

在实际工程中，我推荐优先写迭代版本。递归版本的调用开销虽然很低，但在性能敏感的高频调用路径上，少一次函数调用就少一次栈帧的建立与销毁。而且迭代版本更容易嵌入到其他逻辑里，比如后面要讲的“二分答案”场景，需要反复返回区间边界，迭代版本更好控制。

2.3 开区间写法与左闭右闭的坑

除了左闭右闭，还有一种是左闭右开区间[left, right)，这也是 C++ STL 中大量使用的区间表示法。在这种定义下，right代表的是“第一个不参与搜索的位置”，循环条件变成left < right，因为当left == right时区间为空，不需要继续循环。收缩逻辑也要相应调整：

int binarySearchOpen(const std::vector<int>& nums, int target) { int left = 0; int right = nums.size(); // [left, right) 开区间 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid; // 注意这里不是 mid - 1 } } return -1; }

注意看，在左闭右开区间里，当nums[mid] > target时，mid位置的值已经偏大，所以目标值的搜索范围应该排除mid及其右侧，但右边界本身是开区间，所以直接让right = mid就是正确的。如果你写成right = mid - 1，就会把mid - 1那个位置也排除掉，可能漏掉目标值。

这两种区间定义没有谁对谁错，关键在于你必须在整个函数里保持前后一致。我最常犯的错误是：题目里用的是左闭右闭，我脑子一热把循环条件写成left < right，然后漏判断最后一个元素；或者在左闭右开里用left <= right，直接死循环。所以写二分前第一件事，就是明确你手上的区间到底是什么定义，然后所有边界收缩都严格遵循这个定义。

3. 边界条件与死循环：那些年我们一起踩过的坑

3.1 循环条件到底用 left < right 还是 left <= right

这是初学者问得最多的问题。答案取决于你的区间定义：

• 左闭右闭[left, right]：用left <= right，因为当左右相等时还有一个元素没判断。
• 左闭右开[left, right)：用left < right，因为当左右相等时区间已经空了。

如果你非要混用，比如左闭右闭却写left < right，那么最后剩下的那个元素会被漏掉。解决方法是循环结束后单独判断一下：

while (left < right) { ... } return nums[left] == target ? left : -1; // 补一个判断

这样也能通过，但容易忘。我更建议从一开始就把区间定义写清楚，不要依赖“事后补漏”。

还有一种情况是你要找“第一个不小于 target 的元素”，也就是lower_bound。这种场景下，左闭右开区间写法天然更契合，因为 STL 的lower_bound返回的就是一个迭代器，指向“第一个不小于 target 的元素”，返回的迭代器范围就是[first, last)风格。后面会专门讲。

3.2 mid 的计算：防止溢出

前面提到过left + (right - left) / 2比(left + right) / 2更安全。除了整数溢出，还需要注意当数组长度为偶数时，mid会偏向哪一边。left + (right - left) / 2得到的是“下中位数”，也就是靠左的那一个。如果你需要“上中位数”，可以写成left + (right - left + 1) / 2。

什么时候必须用上中位数？典型场景是查找“第一个大于 target 的元素”，或者处理区间收缩时容易陷入死循环的情况。比如你在收缩边界时写了left = mid（而不是mid + 1），如果 mid 又取下中位数，当right - left == 1时，mid会等于left，然后left = mid会导致 left 永远不变，死循环。这时候你就需要让 mid 偏向右侧，写成mid = left + (right - left + 1) / 2。我见过太多人死循环后随便改 mid 计算，结果越改越乱。正确思路是先确定收缩策略，再反过来决定 mid 是靠左还是靠右。

3.3 查找第一个/最后一个等于目标值的元素

普通二分只能找一个等于目标值的元素，但数组中可能有重复元素。面试和比赛里经常要求你找“第一个出现的位置”和“最后一个出现的位置”。它们的本质区别在于，找到nums[mid] == target后，你不应该立刻返回，而是继续收缩区间。

找第一个等于 target 的元素，依然用左闭右开区间：

int firstEqual(const std::vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; // 即使相等也继续向左收缩 } else { left = mid + 1; } } if (left < nums.size() && nums[left] == target) return left; return -1; }

这个实现的核心是：当nums[mid] >= target时，把右边界收缩到mid，因为可能还有更靠左的等于 target 的元素。循环结束后，left指向第一个大于等于 target 的位置。如果该位置的值正好等于 target，那它一定是第一个等于 target 的元素；否则说明数组里没有 target。

找最后一个等于 target 的元素，稍作变化：

int lastEqual(const std::vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; // 即使相等也继续向右收缩 } else { right = mid; } } // 此时 left-1 是最后一个小于等于 target 的位置 if (left - 1 >= 0 && nums[left - 1] == target) return left - 1; return -1; }

这里巧妙的一点是，我们把“最后一个等于 target”转化为“最后一个小于等于 target”的位置。因为区间是开区间，循环结束后left指向第一个大于 target 的元素，所以left - 1就是最后一个小于等于 target 的元素。如果它等于 target，那就是我们要找的结果。

我建议把这两个函数背下来，不是因为它们有多难，而是因为它们涵盖了“找下界”和“找上界”的核心思想，理解了它们，后面看 STL 的lower_bound和upper_bound就会觉得非常熟悉。

4. 二分查找的变种：不止于“找相等”

4.1 找第一个不小于 target 的元素（lower_bound）

lower_bound解决的问题是：在一个有序数组中，找出第一个大于或等于 target 的下标。如果所有元素都小于 target，则返回数组的大小（可以理解为插入位置）。手写实现很简单：

int lowerBound(const std::vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; }

这个实现和前面firstEqual几乎一样，只是最后不需要再检查相等条件。返回值可以直接作为插入点，比如你在有序数组里不想用std::vector::insert的线性移位，而是想知道新元素应该放在哪里来保持有序，lower_bound就派上用场了。

4.2 找第一个大于 target 的元素（upper_bound）

upper_bound返回第一个大于 target 的下标。手写实现：

int upperBound(const std::vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid; } else { left = mid + 1; } } return left; }

注意这里和lowerBound的唯一区别是判断条件从>=变成了>。如果数组中存在多个等于 target 的元素，lower_bound指向第一个等于 target 的位置，upper_bound指向最后一个等于 target 的位置之后，那么[lower_bound, upper_bound)这个半开区间恰好覆盖了所有等于 target 的元素。这个性质在统计重复元素个数或者处理区间覆盖问题时非常有用。

4.3 在旋转有序数组中查找

“旋转有序数组”比如[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; if (nums[left] <= nums[mid]) { // 左半部分有序 if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { // 右半部分有序 if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; }

思路是：每次计算 mid 后，至少有一半（左半或右半）是严格有序的。如果左半有序，并且 target 落在左半的范围内，就搜索左半，否则搜索右半。注意nums[left] <= nums[mid]里的等号，它处理了数组中可能存在重复元素的情况。如果数组中有大量重复元素，比如[1, 0, 1, 1, 1]，这个判断会退化成近似线性查找，因为无法确定哪边有序。这是旋转数组二分的一个固有局限，如果题目允许重复元素，复杂度最坏会退化到 O(n)，此时需要结合线性扫描或者换用其他思路。

4.4 浮点数二分：解方程、求平方根

二分不只能应用于整数数组，还能用于连续区间上求解方程。比如求一个非负数的平方根，精确到小数点后 6 位。由于浮点数没有“下标”概念，循环条件和边界收缩需要换成基于精度的写法：

double sqrtByBinary(double x, double eps = 1e-6) { double left = 0, right = x; if (x < 1.0) right = 1.0; // 防止 x=0.25 时平方根为 0.5，超出 [0,x] while (right - left > eps) { double mid = left + (right - left) / 2; if (mid * mid > x) { right = mid; } else { left = mid; } } return left; }

注意这里不能使用left <= right这种判断，因为浮点数永远不会精确相等。也不建议用固定迭代次数，除非你知道精度和收敛速度的对应关系。常见的做法是设定一个很小的阈值eps，当right - left小于等于eps时停止循环。另一个陷阱是当x < 1.0时，比如x = 0.25，它的平方根是0.5，大于x本身，所以right初始值不能设为x，至少设为1.0。

浮点数二分在数值计算里非常常见，比如求一个函数在某个区间内的零点、求圆周率近似值、模拟物理中的碰撞时间等。它的核心思想是“二分答案”——给定一个候选值，判断它是否满足条件，再根据结果收缩区间。这也引出了整型最大二分应用：二分答案法。

5. C++ 标准库的二分：STL 中的 lower_bound/upper_bound/binary_search

5.1 使用方式与注意点

C++ STL 已经在<algorithm>头文件里提供了现成的二分查找函数。只要数组有序，你可以直接用，不用自己造轮子。

#include <algorithm> #include <vector> int main() { std::vector<int> data = {1, 3, 5, 5, 7, 9}; // binary_search：返回是否存在目标值 bool found = std::binary_search(data.begin(), data.end(), 5); // lower_bound：返回第一个 >= 5 的迭代器 auto itLower = std::lower_bound(data.begin(), data.end(), 5); // upper_bound：返回第一个 > 5 的迭代器 auto itUpper = std::upper_bound(data.begin(), data.end(), 5); return 0; }

使用binary_search时，不要先调用lower_bound判断返回值是否等于 end，然后再调用binary_search，这样会做两次对数查找。更高效的做法是只调用一次lower_bound，然后判断返回的迭代器是否指向目标值：

auto it = std::lower_bound(data.begin(), data.end(), 5); bool found = (it != data.end() && *it == 5);

注意binary_search返回的是 bool，它不保证返回哪一个等于目标值的元素位置，只告诉你“有没有”。如果你需要位置，必须用lower_bound或upper_bound。

STL 二分基于迭代器实现，意味着它适用于任何随机访问迭代器，比如std::vector、std::array的迭代器，甚至原生指针。对于链表（std::list）这种不具备随机访问能力的容器，用std::lower_bound会退化为线性查找，因为迭代器每次移动只能一步。所以如果你要对链表做二分，需要先把元素拷贝到 vector 里，或者自行设计跳跃结构。

5.2 自定义比较器

STL 二分默认使用operator<来比较元素。如果你排序时使用了自定义比较规则，那么二分时也必须传入相同的比较器，否则结果完全不可预期。比如你有一个自定义结构体Item，按照价格升序排列，想查找第一个价格大于等于某个值的元素：

#include <algorithm> #include <vector> struct Item { int price; int stock; }; int main() { std::vector<Item> items = {{10, 5}, {20, 3}, {30, 8}}; auto comparator = [](const Item& a, const Item& b) { return a.price < b.price; // 按 price 升序 }; // 必须先按该规则排序 std::sort(items.begin(), items.end(), comparator); Item target; target.price = 25; auto it = std::lower_bound(items.begin(), items.end(), target, comparator); if (it != items.end()) { // it 指向第一个 price >= 25 的 Item } return 0; }

一个常见的错是排序用 lambda A，查找用 lambda B，两者逻辑不一致，导致结果错乱。还有就是查找时传入的“伪目标”结构体，必须保证其比较字段被正确初始化，否则未定义行为会在大型项目里以诡异的方式呈现——比如内存越界读，而不是崩溃。

5.3 与手写二分的性能对比

手写二分和 STL 二分在性能上没有本质差别，因为标准库的实现同样是对数复杂度，内部也没有虚函数等额外开销。但在代码可读性和维护性上，STL 版本明显更优。你能少写很多边界处理，尤其是当数组类型是long long、std::string或者自定义对象时，STL 帮你统一了比较逻辑。

不过 STL 二分也有一个“坑”：它要求容器中的元素是有序的，并且排序规则要严格按照小于比较来定义。如果你给一个几乎有序但并非完全有序的数组调用binary_search，结果是未定义的，可能能找到，也可能找不到。很多人在实际项目中用std::sort对数组排序后，又往里面 push 一个新元素，忘记新元素破坏了有序性，然后调用二分查找，查不到就怀疑算法有问题。这是一个典型的“不是算法错，而是数据错”的场景。

6. 常见问题与调试技巧实录

6.1 死循环？打印搜索区间

我调试二分死循环最有效的方法，是在循环开头打印left和right，以及mid。看着区间变化，立刻能发现问题。比如一个经典死循环：

while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; // 应该是 mid + 1 } else { right = mid; } }

当left = 0, right = 1时，mid = 0，如果nums[0] < target，那么left = mid = 0，区间永远不收缩。打印出来你会看到 left 和 right 一直不变。修复方法有两个：改成left = mid + 1，或者将 mid 改成上中位数left + (right - left + 1) / 2。这两个修复方式在不同题里都见过，选哪个取决于你整体逻辑。我的经验准则是：优先考虑是否应该用mid + 1，因为大多数“找边界”问题都可以用收缩下界的方式避免死循环；只有当你必须使用left = mid这种收缩方式时，才把 mid 改成上中位数。

6.2 数组边界越界

越界通常发生在nums.size() == 0时。如果数组为空，左闭右闭写法里right = nums.size() - 1直接变成-1，循环条件left <= right为0 <= -1为 false，不会进入循环，看似安全。但如果你在进入函数前没有对空数组做特殊处理，后面代码里访问nums[left]就会越界。左闭右开写法中right = 0，循环条件left < right为0 < 0为 false，相对安全一些。

另一个越界场景是返回值。lower_bound返回nums.size()表示“所有元素都小于 target”，这个值是合法的下标之后的位置。你拿它直接去nums[result]访问就会越界。所以 STL 版本要求你必须先判断result != nums.size()。在我自己写的算法模板里，我会把“返回下标”的二分接口统一设计成返回-1表示找不到，而把“返回插入位置”的接口设计成允许返回size()，这样两种语义区分清楚，调用方不容易误用。

6.3 如何用二分答案解决实际问题

二分查找不仅能“查值”，还能“求答案”。这种思路在算法竞赛和工程优化里叫“二分答案”：如果一个问题具有单调性——答案越大，某个可行性判断越容易（或越难）——那么你就可以在答案范围内二分搜索，用check(mid)判断当前答案是否可行，然后收缩范围。

举个例子：有 n 根绳子，长度各不相同，你需要把它们切成 k 段等长的小段，问每段最长能有多长？这个问题没有直接的公式，但我们可以二分每段长度len，然后计算所有绳子能切出的总段数sum(nums[i] / len)，如果总段数大于等于 k，说明这个长度可行，可以尝试更大；否则需要减小。代码骨架如下：

double maxLen = *std::max_element(nums.begin(), nums.end()); double left = 0, right = maxLen; while (right - left > 1e-4) { double mid = left + (right - left) / 2; int cnt = 0; for (double num : nums) { cnt += static_cast<int>(num / mid); } if (cnt >= k) { left = mid; } else { right = mid; } }

再比如“给定某日气温，求最晚连续多少天温度都不超过 30 度”“给定一堆作业，判断在 deadline 前能否完成”这类问题，只要你能写出check(mid)函数，二分答案就能把“求极值”转化为“判断可行性”。这个技巧的关键是找到单调性：如果 mid 可行，那么比 mid 更“宽松”或者更“严格”的结果是否一定可行或不可行。画个单调函数图像帮助思考，比闷头写代码高效得多。

6.4 一些调试小技巧

我自己的二分调试习惯可以整理成几个实用小点。

- 写一个暴力验证函数。在小数据集上，用线性查找跑一遍结果，再和你写的二分结果对拍。比如随机生成十万个有序数组，随机生成 target，比较二分返回值是否和线性查找一致。如果对拍通过，基本可以确定边界逻辑没错。

- 针对特殊数据单独测：空数组、单个元素、两个元素、所有元素相等、目标值比最小元素还小、目标值比最大元素还大。这六种情况几乎覆盖了所有边界角落。

- 在函数的入口加断言：assert(nums.empty() || std::is_sorted(nums.begin(), nums.end()));这样一旦你忘记排序，程序会直接报错而不是给你一个错误结果。

- 对于mid的溢出担忧，除了使用left + (right - left) / 2，也可以在 Debug 模式下对数组长度做限制，或者把left、right都声明为long long来彻底避开 int 溢出问题。我在写工程代码时更倾向于用std::size_t和std::ptrdiff_t这类无符号/有符号类型来配合容量，但算法题里还是习惯用int，配合安全的 mid 写法就够了。

• 不要在一个函数里混用多种区间定义。如果你在同一个程序里既写左闭右闭又写左闭右开，建议把两种版本分别封装成命名清晰的函数，比如binarySearchClosed和binarySearchOpen，避免逻辑混乱。

我在实际做项目的时候，还有一个小体会：二分查找最好是作为标准库函数或者自己封装好的工具函数存在，不要在业务代码里一遍一遍手写。因为手写一次，边界条件就可能出一次问题。封装后，你只需要在工具类里把边界处理到极致，其他所有调用方都直接复用，准确性会高很多。我自己的 C++ 工程里就维护了一个 small_algo.h 头文件，里面放了我反复验证过的二分查找、lower_bound、upper_bound 和旋转数组查找，每次新建项目都会把它带上。你会发现，虽然这些代码加起来不到一百行，但它为你省下的调试时间是远远超过当初写下它们所花的时间的。