企业官网建设流程全解析

二分查找大概是所有算法里“看起来最简单、写起来却最容易翻车”的一个。网上搜“二分查找”，能翻到一大堆模板，可一旦把问题从“找等于 target 的数”换成“找第一个大于等于 target 的数”“找最后一个小于等于 target 的数”，或者要求在有重复元素的数组里定位左右边界，很多人当场就开始左右横跳。我见过不少算法工程师面试候选人，能把这个基础题写得完全正确的比例，说实话并不高——这不是基础知识不扎实，而是这个算法本身存在大量“边界细节陷阱”，稍不注意就是死循环或者越界。

这篇文章不打算再贴一份教科书式的模板了。我想从一个“踩过坑、填过坑”的从业者角度，把二分查找的真正难点拆开讲清楚：它到底在找什么、边界到底怎么定、变体怎么推、二分答案思想怎么用、遇到死循环怎么排查。全文围绕的核心只有一个标题里的词——二分查找，但我会把它放到真实的编码场景里去聊，保证你看完能少走很多弯路。

1. 先想明白二分查找到底在找什么

1.1 它本质是在“收敛分界点”，而不是单纯的搜索

很多人把二分查找理解成“在有序数组里找一个数”，这个理解不能说错，但太窄了。真正理解二分查找，要换一个角度：它是在一个单调序列里，快速收敛到某个“分界点”。这个分界点可能是目标值本身，也可能是“第一个满足某条件的位置”“最后一个满足某条件的位置”，甚至根本不是一个数组里的位置，而是一个抽象的答案值。

举一个最直观的例子，猜数字游戏：我心里想一个 1 到 100 的整数，你每猜一次我只告诉你“大了”还是“小了”，你最快几次能猜中？答案是 7 次左右，因为每次猜测都能把范围砍掉一半，100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1，这就是 log2(n) 次。这个过程中你做的不是“线性扫描”，而是不断问同一个问题：“目标值在当前范围的前半段还是后半段？”每一次回答都让你丢弃一半的候选空间。

这个思路的本质，是利用信息的单调性做筛选。一个数组如果是递增的，那么一旦发现 arr[mid] < target，就能确定 arr[mid] 左侧的所有元素也都不可能是 target；反过来如果 arr[mid] > target，右侧也全部可以排除。之所以敢这样“大砍一刀”，靠的就是有序性，“所有左侧都小于它”这条信息让我敢整体放弃。

所以，二分查找能不能用，取决于你的数据或你的判断函数是不是单调的。不单调，砍掉一半的推理就不成立；单调，才能放心把范围缩到最后 1 个候选位置。

1.2 比较次数为什么是 log n

每次迭代，搜索区间缩小一半，那么经过 k 次迭代之后，区间长度变成 n / 2^k。当区间长度缩到 1 的时候，你就找到了答案，所以 k = log2(n)。n 等于 100 万的时候，log2(1000000) 约等于 20，也就是说只需要 20 次比较就能定位到目标元素。

这个数字意味着什么？顺序查找在最坏情况下要做 100 万次比较，二分查找只需要 20 次。这就是“指数压缩”带来的威力——每一次比较不是排除一个元素，而是排除一半元素。理解这一点，你才能理解为什么在数据库索引、路由表查找这种动辄百万级数据的场景里，二分查找是最底层的基石之一。

这个数学关系还有一个直接后果：问题规模扩大一倍，二分查找的耗时只增加 1 次比较。这是任何 O(n²) 算法都做不到的。当你拿到一个新问题，如果能找到单调的验证函数，优先考虑二分，因为它的复杂度增长实在太友好了。

1.3 前 100 字内的关键词铺垫

说了这么多，其实就想传达一件事：二分查找不是“在数组里找一个值”，而是“在一个单调空间里快速收敛到一个位置”。后面的所有技巧、变体、坑，全部建立在这个认知之上。你把这个想清楚了，写代码时的每一步才有依据，而不是死记模板。

2. 两个最关键的决定：区间定义与 mid 取整方向

2.1 左闭右闭还是左闭右开：先选一个并坚持到底

写二分查找，第一个要拍板的问题是：你的搜索区间是[left, right]（左闭右闭）还是[left, right)（左闭右开）。两种写法都能对，但混着用一定会出事。

左闭右闭是新手最容易理解的写法：

int binarySearch(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; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

这里的关键在于：left和right指向的元素都还没有被排除，所以循环条件是left <= right。当nums[mid] < target时，mid 及其左侧元素全都可以排除，所以left = mid + 1；当nums[mid] > target时，mid 及其右侧全都可以排除，所以right = mid - 1。

左闭右开则稍微抽象一些：

int binarySearch(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 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; // 保证区间左闭右开 } return -1; }

左闭右开的语义是：区间只包含 left 到 right-1 的位置，right 本身不参与检查。所以当nums[mid] > target时，可以把 right 设置为 mid，因为 mid 这个位置虽然被排除了，但它可以作为右边界继续切分。两种写法对应不同的循环条件，一个用<=，一个用<，差别就来自区间的封闭性。

我的个人建议是：用左闭右闭，然后永远不要换。理由有二：一是符合直觉，新手不容易困惑；二是转换为“找左边界”“找右边界”变体时，思路更顺畅，后面你会看到。

2.2 mid 的计算为什么必须写成 left + (right - left) / 2

这是二分查找最常见的隐藏 bug 之一。很多人习惯写(left + right) / 2，在 small case 下没问题，但当 left 和 right 都接近 int 上限时，left + right会先溢出成负数，再除以 2 就得到一个错误的位置，程序直接崩或者死循环。

稳妥写法是：

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

这个式子等价于(left + right) / 2，但因为先做了减法，两个大数相加的溢出问题就规避了。Java 里也可以用无符号右移：

int mid = (left + right) >>> 1;

>>>这种无符号右移方式在处理负数时也能得到正确结果，很多标准库源码里就是这么写的。C++ 和 Python 一般用left + (right - left) / 2就足够了。

还有一个细节容易被忽略：当区间长度是偶数时，mid 取的是中间偏左那个位置。如果 right - left = 1，区间里只有两个元素，mid 等于 left。这个现象在死循环问题里很重要，我在第 5 节会专门展开。

2.3 循环条件与更新策略的配对关系

循环条件、更新策略、mid 取整方向，这三个东西是绑定的，不能随意换：

只要你改变了其中一个条件，其他两个必须跟着调整。我见过太多线上事故，就是因为某个人在某次重构中把left < right改成了left <= right，然后 mid 的排除逻辑没同步改，于是死循环瞬间出现。

记住培养一个习惯：写完一个二分查找，先在心里跑一遍“区间长度为 1”和“区间长度为 2”的情况。这两个小 case 能帮你抓住绝大多数边界错误。

3. 三个高频变体：等值、左侧边界、右侧边界

3.1 查找值不一定存在：标准等值查找的完整写法

送一个可复制的 C++ 版本，注意我写的注释：

// 在有序数组 nums 中查找 target，存在返回索引，不存在返回 -1 // 模板：左闭右闭区间 int binarySearch(vector<int>& nums, int target) { int left = 0, right = (int)nums.size() - 1; 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; }

这套代码的核心逻辑：每次比较之后，要么直接命中返回，要么排除掉 mid 和它一侧的所有元素。循环结束时left > right，说明 target 不在数组里。它的缺点是：当数组里有重复元素时，返回的可能是任意一个等于 target 的位置，不能保证是最左或最右。

3.2 找第一个等于 target 的位置：lower_bound 思想

面试里真正爱考的是有重复元素的场景。比如数组[1, 2, 2, 2, 3, 4]，target = 2，要求返回第一个 2 的下标，也就是 1。

思路和等值查找略有不同：当nums[mid] == target时，不要急着返回，而是继续把右边界向左收，直到区间里只剩下最左边那个 target。

// 查找第一个等于 target 的下标，不存在返回 -1 int findFirst(vector<int>& nums, int target) { int left = 0, right = (int)nums.size() - 1; int ans = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ans = mid; right = mid - 1; // 继续往左边找 } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return ans; }

核心就一句话：命中之后记录答案，但继续收缩右侧。同理，找最后一个等于 target 的下标，就是命中之后记录答案，然后left = mid + 1继续向右边收缩。

这个操作本质上就是 C++ 里的lower_bound和upper_bound的变体。把“等于”改成“大于等于”“小于等于”，就可以得到第一个大于等于 target 的位置、最后一个小于等于 target 的位置。这些变体在很多场景里比“精确查找”更常用。

3.3 一个通用模板：用“排除法”推导所有变体

我总结过一个模板，能覆盖绝大多数查找变体，核心是把问题抽象成查找满足条件的最小值 / 最大值：

// 查找左边界：第一个满足 check(mid) 的下标 // 例如 check(mid) = (nums[mid] >= target) int lowerBound(vector<int>& nums, int target) { int left = 0, right = (int)nums.size(); // 区间 [left, right) while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; // mid 可能是答案，保留 } else { left = mid + 1; // mid 肯定不是答案，排除 } } return left; }

这个lowerBound就是“返回数组里第一个 >= target 的位置”。如果不存在这样的位置，返回 nums.size()。拿到这个函数之后，很多问题都能秒解：

• 找第一个等于 target 的：lowerBound(target)，再检查该位置的值是否等于 target。
• 找最后一个等于 target 的：lowerBound(target + 1) - 1，如果该位置的值等于 target，就找到了。
• 找第一个大于 target 的：lowerBound(target + 1)。
• 找最后一个小于等于 target 的：lowerBound(target + 1) - 1。

这个模板的妙处在于，你只需要写好“判断条件”，剩下的边界逻辑都一致：左闭右开区间，right = mid 保留候选，left = mid + 1 排除非候选。它比“等值+分左右”的套记更不容易写错。

我推荐所有人在面试前把lowerBound这个版本背到肌肉记忆。因为它的语义清晰，从它推导其他变体只需要加减 1，几乎不存在死循环风险。

4. 二分查找的进阶玩法：二分答案与真实场景

4.1 “答案本身也能被二分”：经典二分答案题

二分查找不一定作用在数组下标上，它也可以作用在答案的值域上。这个思路叫“二分答案”，常用于最优化问题：把“求最优解”转化为“验证某个答案是否可行”。

一个经典的例子：给定 n 个果实，重量分别是 w1, w2, ..., wn，要把它们装进 k 个容量相同的袋子里，每个袋子里只能装连续的一段果实（比如按顺序采摘不能打乱），求能满足所有果实装下所需的最小袋子容量。

这个问题直接求最小容量很难，但是“给定一个容量 X，判断是否能装完”却很简单——只要贪心地从左往右塞，满了就换新袋子，最后看袋子数量是否超过 k 就行。于是问题就变成了：在容量值域里二分，找到“第一个能装完的最小容量”。

bool canFit(vector<int>& w, int k, int cap) { int count = 1; int cur = 0; for (int weight : w) { if (cur + weight > cap) { count++; cur = weight; } else { cur += weight; } } return count <= k; } int minCapacity(vector<int>& w, int k) { int left = 1, right = accumulate(w.begin(), w.end(), 0); int ans = right; while (left <= right) { int mid = left + (right - left) / 2; if (canFit(w, k, mid)) { ans = mid; right = mid - 1; } else { left = mid + 1; } } return ans; }

这个模式的通用特征是：答案范围可枚举，且单调性成立。容量越大，越容易装完，所以可以二分。如果你发现一个问题“很难直接求，但很容易验证某个解行不行”，那大概率可以二分答案。

4.2 IP 归属地查询怎么用二分查找

另一个实际工程场景是 IP 归属地查询。全球几十万条 IP 段，每条 IP 段有起始地址和结束地址，要判断一个 IP 落在哪一段。朴素做法是从头扫到尾，每条查询 O(n)，并发一上来直接炸掉。

正确做法是：先把所有 IP 段按起始地址排序，然后把问题转化为“最后一个起始地址 <= 目标 IP 的段”，这不就是二分查找的变体吗？用上一节的lowerBound(target + 1) - 1或者手写一个“查最后一个小于等于目标值的位置”，就能在 O(log n) 时间内定位候选段，再检查目标 IP 是否落在该段的结束地址内。

这也是为什么很多基础数据结构在大型系统里依然生命力旺盛的原因：数组虽然简单，但配合二分，查询速度吊打不少花里胡哨的结构。只要数据是静态加载、构建时排好序，二分查找就是最经济的选择。

4.3 其他你意想不到的二分应用

• “寻找峰值”问题：nums[i] vs nums[i+1]的趋势判断是单调的，可以二分找到任意一个峰值。
• “局部最小值”问题：同样用相邻比较的单调性。
• “两个有序数组的中位数”：值域二分或者下标二分，是算法题里比较进阶的考法。
• “浮点数二分”：求方程的根，比如f(x) = x^2 - n = 0的平方根，精度要求用right - left > 1e-7控制。

浮点数二分有个注意点：循环条件里不能再写 left <= right，必须用精度差来判断，比如while (right - left > 1e-7)。否则浮点数的精度问题会导致死循环。

5. 死循环与边界 Bug 的排查实录

5.1 最常见的死循环是怎么产生的

很多人在写“找左边界”的变体时，会写出这样的代码：

while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; // 如果把 mid+1 误写成 mid } else { right = mid; } }

当区间长度为 2 时，mid等于left。如果此时nums[mid] < target成立，left = mid就相当于 left 没有变，区间永远不缩小，死循环就出现了。这就是 2.2 节提到的“mid 偏左”特性带来的陷阱。

解决办法：排除左侧时，务必写成left = mid + 1。因为 mid 已经被检查过且不可能是答案，所以必须彻底排除它。“排除右侧时可以保留 mid”，是因为 mid 有可能是答案，所以 right = mid 是安全的。这一放一收的逻辑，是二分查找不会死循环的根本保证。

5.2 一套百试不爽的自测方案

我不管写什么二分，写完都会立刻用这几组测试数据快速过一遍：

1. 空数组（很多实现会直接越界，先判空）。
2. 数组只有一个元素，且 target 存在/不存在。
3. target 小于数组最小值。
4. target 大于数组最大值。
5. 数组所有元素都等于 target（测左边界/右边界时非常有效）。
6. 区间长度为 2 时，确保区间能收敛。

这个自测清单其实就是在快速验证三件事：边界更新是否会正确排除元素、循环条件是否能正常退出、返回值是否符合预期。我建议你也把这套清单固化下来，线上改代码之前先跑一遍。很多二分相关的线上问题，不是逻辑多难，而是没人做这套验证。

5.3 排查步骤：从现象反推根因

遇到死循环，第一步不是打日志，而是在纸上把 left、right、mid 的前几轮迭代手工算一遍。规律是：死循环几乎都出在区间长度为 2 或 3 的时候。你只需要把注意力集中在最后一两轮，拿笔推一次，就能很快发现是 left 没动、right 没动，还是 mid 一直在原地。

第二个常见现象是数组越界。比如 lowerBound 返回了 n，然后你去访问 nums[n]，崩了。遇到这种情况，检查你的调用端加了判断没有：应该先判断返回位置是否等于 n，再访问数组元素。

第三个现象是“结果总是偏左一位或右一位”。这是返回值语义没对齐——比如你想找“最后一个 <= target 的位置”，但你用的是“第一个 >= target 的模板”，结果当然差一。遇到这种问题，建议把模板退回到 lowerBound，用“加减 1”来推导目标位置，而不是现场改条件。

5.4 我是怎么彻底记住这些规则的

说一个我自己的土办法：把区间想成“活着的人排队”。left是当前可能成为答案的最左一人，right是“第一个绝对不可能是答案的人”。左闭右开区间[left, right)里站着的都是“嫌疑人”。每次检查 mid 这个人：

• 如果他不满足条件，就让他出队，所以left = mid + 1。
• 如果他满足条件，说明答案可能是他或者他左边的人，所以保留他，right = mid。

这个比喻能覆盖掉 95% 的“边界更新错误”。每次你犹豫left = mid还是left = mid + 1，问自己一句：”mid 已经被排除嫌疑了吗？“如果排除了，就必须 +1。这套思路我在带新人和面试候选人时反复讲，反馈普遍很好。

6. 常见的二分查找快问快答

为了让你以后写代码时能快速自查，我把最常见的几个问题整理成了一张速查表：

6.1 我每次写完会做什么检查

拿到一个新的二分题目，我的流程大概是：

1. 先确认“答案”是数组下标，还是抽象值域。
2. 确认单调性：答案变大/变小是否导致判断结果单调变化。
3. 选择模板：如果找等值，用标准模板；如果找边界，用 lowerBound 模板。
4. 写完跑自测清单（空数组、单元素、边界值、重复元素）。
5. 如果有时间，再想想“结果是否满足我最初定义的语义”。

这个方法看起来很笨，但它真的能在面试和实际工作中救我很多次。二分查找的错误不是智力问题，而是“没有系统验证”的问题。

6.2 最后的个人体会

做了这么多年算法相关的底层和工程工作，我越来越觉得二分查找是一个“看起来简单、实际上考你严谨性”的算法。它不像动态规划那样需要灵光一闪，也不像图论那样需要大而全的建模能力，它就是纯粹地考你能不能把边界条件想清楚、能不能把单调性用对。

如果你正在准备算法工程师的面试，别把二分查找只当作初阶题跳过。我建议你刻意练习一下：找重复元素的左边界和右边界、lowerBound 的泛化形式、二分答案思路，按这套逻辑全部推一遍，你的算法基本功会扎实很多。如果你已经在写业务代码，遇到“海量数据查找”“区间命中”“可行解优化”这类问题，多想一想二分——它可能不是最炫的方案，却往往是最可靠、最可控的解法。