企业官网建设流程全解析

二分查找可能是算法题里最“看着容易、写起来拉胯”的经典了。数组越长，它越显得无所不能；数组越短，它反而容易让你怀疑自己是不是连幼儿园算术都不会。面试笔试、PTA函数题、LeetCode周赛，几乎没有哪个环节能躲开它。但每次看到有同学在while循环里调半天边界，或者把mid = left + (right - left) / 2写错成(left + right) / 2，我都觉得这真不是智商问题，而是这套东西有太多“坑”藏在细节里，没人给你讲透罢了。

这篇我想聊的是我对二分查找的完整认知——不是只给你一个模板背下来，而是把它拆开看：为什么它能做到对数复杂度、为什么不同写法结果不一样、为什么会有死循环，以及它怎么从“查数组”升级成“二分答案”这个大杀器。顺便结合 PTA 上那道经典的二分查找函数题，讲一讲评分点都藏在哪里。适合刚入门算法、正在准备笔试面试、或者被各种边界问题折磨到崩溃的同学。

1. 二分查找到底在做什么——原理拆解

1.1 从一个猜数字游戏讲起

先想一个特别朴素的问题：让你从 1 到 100 里猜一个数字，对方只告诉你“大了”或者“小了”，你会怎么猜？

正常人不会从 1 开始一个一个问。最稳的策略是直接猜 50。如果对方说“小了”，范围马上缩到 51 到 100；如果“大了”，范围缩到 1 到 49。每猜一次，范围大约缩小一半。最多猜 7 次，你总能锁定答案。这就是二分查找最朴素的生活原型。

这个例子里有个非常关键的事实：你之所以敢猜 50，是因为你默认了“数字大小是有顺序的”。如果不排序、随机乱序，猜 50 完全不给任何信息。所以二分查找的第一个前提就是：数据必须存在某种可以比较大小的顺序，也就是通常说的“有序数组”。

1.2 有序性为什么重要——核心是“排除方向”

很多人能背二分查找的代码，但被问到“为什么数组必须有序”时，只能答“因为教材这么说的”。其实本质就一句话：有序性让数组具备了“方向”。

假设数组从小到大排列，你拿arr[mid]和target比较：

• 如果arr[mid] == target，直接命中，不用继续；
• 如果arr[mid] < target，说明target比中间值大，又因为数组从左到右递增，所以target一定在mid右侧，左侧整个半区可以直接扔了；
• 如果arr[mid] > target，同理，target一定在mid左侧。

所以每次比较，不是“猜一次少一个候选”，而是“猜一次杀掉一半候选”。这就是它和线性扫瞄的本质差别：线性查找每次排除一个，二分查找每次排除一半。对应的复杂度对数，元素从 1024 涨到 100 万，二分查找的步数其实也就从 10 涨到 20 而已。

1.3 二分查找的本质：可行性判定函数

我喜欢把二分查找看成一件更高级的工具。它的本质不是“在有序数组里找一个数”，而是在一段连续的区间上，找一个“分界点”——左边满足某个性质，右边不满足，或者反过来。

举个例子：arr = [1, 3, 5, 7, 9]，要找 5。你其实可以把数组看成每个位置上的“这个数是否小于 5”：

• 1 < 5为真
• 3 < 5为真
• 5 < 5为假
• 7 < 5为假
• 9 < 5为假

这个真假序列是真、真、假、假、假，中间有一个清晰的“分界点”，二分查找就是在找这个分界点。一旦你把问题转换成“判断某个位置左边全部为真、右边全部为假”，理解各种变种题就顺了，包括后面要讲的lower_bound、upper_bound，以及二分答案，全都能统一到这同一个框架下。

2. 手写二分查找——三种区间模板和它们的爱恨情仇

2.1 模板一：闭区间[left, right]

最常见、也最好理解的写法：

int binary_search(int nums[], int n, int target) { int left = 0, right = n - 1; // 闭区间 [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 - 1; // 右侧全部排除 } } return -1; }

这里while (left <= right)对应的意思是：当区间里至少还有一个元素时，继续循环。所以循环结束后，left = right + 1，区间彻底空了，此时返回-1表示没找到。这种写法最直观，新手最容易接受。

唯一要注意的坑是mid的计算。写成(left + right) / 2在left和right都很大的时候可能整型溢出。虽然刷题时数组长度很少到 10 亿级别，但面试官喜欢问，所以还是养成写left + (right - left) / 2的习惯更稳。这个损失不了几个字节，纯赚的。

2.2 模板二：左闭右开[left, right)

C++ 的 STL 容器几乎全用“左闭右开”的区间约定，所以刷题时你也会经常看到这种写法：

int binary_search(int nums[], int n, int target) { int left = 0, right = n; // 左闭右开 [left, right) while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; // 注意：这里返回的是“第一个 >= target 的位置” }

这里的变化比较微妙：

• right指向的是最后一个元素的下一个位置，所以初始化为n而不是n - 1；
• 循环条件变成left < right，因为当left == right时区间是空的；
• 当nums[mid] < target时，说明mid及左侧都不可能是目标，所以left = mid + 1；
• 否则（也就是nums[mid] >= target时），mid可能是目标，保留它，所以right = mid，不是mid - 1。

这个写法其实直接实现了lower_bound——返回第一个不小于target的位置，在后文会细讲。如果你要找target本身是否存在，拿这个位置再判断一下值即可。

2.3 模板三：开区间(left, right)

还有一种写法让区间两端都不包含：

int binary_search(int nums[], int n, int target) { int left = -1, right = n; // 开区间 (left, right) while (left + 1 < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; } else { right = mid; } } return right; // 第一个 >= target 的位置 }

这个写法的好处是mid 永远不会和 left 或 right 相等，因为 left 初始为 -1、right 初始为 n，而left + 1 < right保证了 mid 至少比 left 大 1、比 right 小 1。这意味着不管怎么更新，left = mid或right = mid都不会造成死循环。等你想清楚了各种奇奇怪怪的边界，再回到这个模板，会感叹它是真的优雅。

但平时我还是建议新手从闭区间模板入手，因为最符合直觉。当闭区间写熟了，再把“区间开闭”的变换当作一种思维体操去理解，收益会更大。

2.4 中位数陷阱：左中位还是右中位

写二分查找时，mid = (left + right) / 2默认取的是左中位（向下取整）。大部分情况没问题，但一旦你的更新逻辑里含有left = mid这种，左中位就会导致mid永远等于left，从而死循环。

来一个具体场景。查找“最后一个等于 target 的位置”：

int search_last(int nums[], int n, int target) { int left = 0, right = n - 1; while (left < right) { // 注意不是 <= int mid = left + (right - left) / 2; // 左中位 if (nums[mid] <= target) { left = mid; // 这里埋着死循环！ } else { right = mid - 1; } } return left; }

假设nums[mid] <= target恒成立，那么 right 不动、left 每次变成 mid，而 mid 一直是 left，循环永远出不来。解决办法是取右中位：

int mid = left + (right - left + 1) / 2; // 右中位，向上取整

右中位会在两元素时偏向右边，左中位偏向左边。口诀就是：用左中位就配left = mid + 1，用右中位就配right = mid - 1；一旦需要left = mid，得用右中位；一旦需要right = mid，得用左中位。这是我见过最容易踩、也最防不胜防的坑。

3. 二分查找的变种与真实应用场景

3.1 lower_bound 和 upper_bound 到底是什么

实际工程和算法题里，查“等于某个值”其实没那么多需求，更多时候是要查位置边界。比如：

• lower_bound：返回第一个>= target的位置；
• upper_bound：返回第一个> target的位置。

这两个函数加一起，就能轻松计算一个有序数组中某个值的出现区间。C++ 的std::lower_bound和std::upper_bound帮你实现了，但面试时经常被要求手写。用刚才左闭右开模板，就是现成的：

// 手动实现 lower_bound int lower_bound(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; } } return left; }

它的本质在前面也提到了火花：nums[mid] < target时，说明 mid 左侧全不行，排除左侧；否则 mid 可能是答案，保留之。把自己训练成“判定函数”思维，这种题目根本不需要背，推一遍就能写出来。

3.2 二分答案：把最优化问题变成判定问题

这个扩展我认为是整个二分查找里最有价值的升华，比单纯查数字有用得多。

场景：有n段木头，长度分别存进数组里，要切割成k段长度相等的小段。问每段最长能切多长？

直接算“最长”很难，但如果你给定一个长度len，去判定“能不能切出 k 段”，这就非常简单了——把每根木头整除一下，累加段数，看是否够k。于是真正的最长变成了一个“最大可行值”的搜索问题：可行就继续往长了试，不可行就往短了缩。这完全可以二分查找。

写出判定函数：

bool can_cut(int len, vector<int>& wood, int k) { int count = 0; for (int w : wood) { count += w / len; } return count >= k; }

然后对答案二分：

int max_len(vector<int>& wood, int k) { int left = 1, right = *max_element(wood.begin(), wood.end()); while (left < right) { int mid = left + (right - left + 1) / 2; // 右中位，避免死循环 if (can_cut(mid, wood, k)) { left = mid; // 可以，继续往长试 } else { right = mid - 1; // 不行，缩短 } } return left; }

用到的思想恰恰是 1.3 节说的“可行性函数分界”：短的可行，长的不可行（注意方向要根据题意变），找那个分界点。

这种“二分答案”技巧在算法竞赛里太常见了，典型模型有：

• 求最小化最大值（比如把数组拆成m个子数组，让每个子数组和的最大值最小）；
• 求最大化最小值（比如给牛棚位置，让相邻牛之间最短距离最大）；
• 在浮点域上二分求方程的根或最优近似解。

遇到这类题，第一反应不要想怎么贪心或动态规划，先想：能不能把“求最优值”改写成“判定某个值可行不可行”？如果能，那就二分答案。判定函数越简单，这个思路越划算。

3.3 浮点数二分：精度控制有讲究

整数的二分可以盯着边界，浮点数就没这么讲究了，一般用误差阈值控制终止：

double sqrt_binary(double x) { if (x < 0) return -1; double left = 0, right = x; // 处理 x 小于 1 的情况：右边界至少是 1 if (x < 1) right = 1; while (right - left > 1e-7) { // 精度给到 1e-7 double mid = left + (right - left) / 2; if (mid * mid < x) { left = mid; } else { right = mid; } } return left; }

浮点数二分不需要担心死循环，因为mid永远在 left 和 right 之间，且区间长度不断减半。你唯一要决定的是误差阈值。阈值太小会多跑几十次循环，但每次循环开销也不大，一般建议比题目要求精度高 2 个数量级，比如要求保留 6 位小数，就用到1e-8这种量级。

3.4 PTA 函数题实战：评分卡在哪里

再来专门说说 PTA（拼题A）上那道经典的二分查找函数题。题目一般是这样：

Position BinarySearch(List L, ElementType X);

给定一个递增的线性表L和元素X，要求返回X在表中的位置，找不到就返回NotFound。很多同学的代码能跑通本地样例，但提交就是错或者有超时，原因往往在几个细节上：

第一，下标从 1 开始。PTA 的List结构通常这么定义：

typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; // 线性表最后一个元素的位置 };

而Position一般约定为 1 到Last之间的值，Data[1]存第一个元素，Data[0]通常空着或者不用。所以你的left = 1, right = L->Last，而不是从 0 开始。

第二，中间值写成(left + right) / 2，又把left + right塞进固定 int。在评测环境里，Position有可能是 int、long，当表特别大时溢出风险就来了。用left + (right - left) / 2或者位运算右移，才能避免。

第三，循环退出条件。如果你写成while (left < right)，再配合right = mid - 1，可能漏掉left == right时那一次检查。更稳的做法是用while (left <= right)闭区间，直接把最终命中节点也查了。

对比一下常见的错误写法：

Position BinarySearch(List L, ElementType X) { Position left = 1, right = L->Last; while (left < right) { // 错：会漏查 left == right 的情况 Position mid = (left + right) / 2; if (L->Data[mid] < X) left = mid + 1; else if (L->Data[mid] > X) right = mid - 1; else return mid; } if (L->Data[left] == X) return left; else return NotFound; }

这个其实也能过，但容易出问题的地方在于：如果Last == 0，也就是空表，left = 1已经越界访问了。真正稳的写法就要先判空，再进入二分，最后再决定返回值。很多同学 PT A 上卡在三分、两分，不是算法不懂，全是这些细枝末节的文件。

4. 高频 bug 与排查技巧

4.1 死循环的内幕

死循环是二分查找最大的杀手。前面简单提过，现在系统梳理一下它的产生条件。

一、更新分支里出现了left = mid或right = mid，同时 mid 取位方向不合适，导致 mid 永远等于边界。比如left = mid却取了左中位，两元素时 mid 就是 left，left 不前进，永远循环。同理，right = mid却取了右中位，也会卡死。

二、循环条件是left <= right，但你的边界更新逻辑有时left或right根本不移动。最典型的错误是把left = mid - 1写成left = mid，或者right = mid + 1写成right = mid。闭区间时每次排除的是mid ± 1，如果漏掉 ±1，就可能在两个值之间来回横跳。

三、对区间开闭理解混乱。比如左闭右开区间[left, right)，却用right = mid - 1，这会导致区间越来越离谱，循环次数失控。

死循环在我看来几乎都是“取中位方向”和“边界更新方向”不匹配造成的。记住 2.4 节的口诀，这种问题基本上能绕开一条命。

4.2 边界错位与返回值混乱

另一类高发问题不是死循环，而是返回的位置差了一位。

写lower_bound时，到底是返回第一个大于等于 target 的位置，还是最后一个小于 target 的位置？很多人写完心里没底，一跑样例好像对，换一组边界就错。

这种问题最好的解法就是拿最小规模的边界案例手工验证。比如数组[2, 3]，分别试 target = 1、2、3、4，手工推一遍你的代码，看返回结果是否符合预期。

• target = 1，应当返回 0（第一个 >= 1 的是第 0 个）；
• target = 2，应当返回 0；
• target = 3，应当返回 1；
• target = 4，应当返回 2（越界位置不算错，工程上常用这个哨兵位置表示“不存在”）；

如果这四个点都过了，你的 lower_bound 逻辑基本稳了。

4.3 三个调试技巧

我自己的实战经验里有三个特别管用的调试技巧，分享给大家：

技巧一：打印左右边界。在 while 循环里加一行printf("left=%d right=%d mid=%d\n", left, right, mid);，配合小样例跑一遍，看区间缩小轨迹是否符合直觉。死循环一眼就能看出来：某行输出里 left 和 right 半天不变化。

技巧二：断言区间收缩性。每次循环里可以加一个断言：assert(mid != left || mid != right)，保证 mid 不会等于两个边界之一。如果left = mid而 mid 又等于 left，断言立刻炸出来，省得你干瞪眼。

技巧三：把目标值换成边界值。如果你不确定返回结果对不对，直接拿数组第一个元素、最后一个元素、甚至比第一个还小的值、比最后一个还大的值去测试。大多数边界 bug 藏在这四个点上。

我把常见错误整理成一个速查表：

4.4 一个综合例子：查找旋转排序数组中的最小值

把前面所有知识串起来的经典题：nums本质是有序数组经过一次旋转，比如[4, 5, 6, 7, 0, 1, 2]，要找最小值。虽然数组不是全局有序的，但它可以分为两个递增段，且分界点就是最小值。

思路还是要找“第一个小于或等于末尾元素的位置”。假设末尾元素是nums[n-1]，那么数组中nums[x] <= nums[n-1]这个性质，在分界点右侧恒成立，左侧恒不成立。用二分找这个分界点即可：

int find_min(vector<int>& nums) { int n = nums.size(); int left = 0, right = n - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[n - 1]) { left = mid + 1; // 说明 mid 在左侧递增段，最小值在右边 } else { right = mid; // mid 在右侧，继续往左找更小的分界 } } return nums[left]; }

这个题没有直接“找 target”，而是用“判定函数”扫描区间，但它依然是二分查找。写到这里我特别想说一句：别把二分局限在“有序数组里查值”，要把思维升级成“找单调性质的分界线”。一旦想通，你在刷题档次上会有肉眼可见的跨越。

5. 学习路径与工程应用感悟

5.1 怎么练习最有效

如果想系统地把二分查找彻底吃透，我的建议是别急着刷一堆题，先把基础模型题练熟，再上变种：

• 第一梯队（手写基础）：数组里查找 target，以及 lower_bound/upper_bound 的手写实现，练到闭眼能写不卡壳；
• 第二梯队（经典变种）：查找第一个等于 target/最后一个等于 target 的位置、查找插入位置、旋转排序数组最小值；
• 第三梯队（二分答案）：拆数组最大最小值、分木头、分配饼干这类最优化题目，练到能熟练把最优化问题改写成判定 function。

做题时有个习惯很强推：每次写二分，把区间写法和 mid 的取法定下来了，再动循环体。不要临场“灵机一动”，模板定式很重要。等代码跑通了，再尝试把闭区间改成左闭右开，或者开区间，体会一下不同写法对边界的影响，这一步对面试时临场解释非常有用。

5.2 工程里的二分不止在数组里

很多人以为二分查找只在刷题时用得到，工程里没什么存在感。这是个很大的误解。举几个真实的例子：

• 程序 bug 排查：版本管理系统里类似 “git bisect” 的功能，本质就是二分定位。你有几百个提交，其中某一个引入了 bug，每次都取中间那次提交来测试，能快速定位出具体是哪一次引入的问题。
• 数据库索引与文件系统：在有序索引结构上做查找，绕不开二分。B+ 树的节点内部通常会用二分查找定位 key，不是线性扫。
• 机器学习与调参：在某个单峰区间上搜索最优超参或学习率时，如果满足条件可以先用二分/三分快速逼近，比网格搜索效率高得多。
• 数值计算：求方程的根、查找临界点，二分法是最简单最稳的逼近方法之一。

所以我说二分查找不像那些花哨的动态规划惊世骇俗，但它是真正的“朴素而强大”。不是每个题目都能动态规划，但每个有序场景下你都能想到二分。

写到这里，我最大感觉是：二分查找的难度根本没在算法思想上，全在表达细节上。理解它本质上是在找“性质分界点”之后，代码怎么写都不容易飘。如果你手头有 PTA 或者 LeetCode 刷题任务，别急着背模板，先拿出一张纸，把 left、right、mid 之间的关系画出来，把闭区间和左闭右开的差异试出来，后面真的会舒服很多。我自己当年就是在“左闭右开”这个怪圈里绕了整整一周才彻底想明白，现在回头看，才是真正值回票价的那一周。