企业官网建设流程全解析

二分查找这个算法，我在面试别人的时候几乎每次都会问，自己也反反复复手写过无数遍。它看起来太简单了——一个有序数组，找一个目标值，折半、判断、再折半，循环几次就能出结果。但真正能在白板上一次写对、把边界条件讲清楚的人，其实不多。这个算法最迷人的地方在于，它用 O(log n) 的时间解决了一个最朴素的查找问题：在四十亿条有序数据里定位一个目标值，最多只需要比较三十二次。这背后是计算机科学里非常重要的一种思维——每次迭代都砍掉一半的搜索空间。

这篇内容想把二分查找这件事彻底讲透。不管你是刚开始学数据结构与算法的新手，还是在准备算法工程师面试、刷 LeetCode 的进阶玩家，甚至只是工作中要处理有序数据的检索、要理解数据库索引原理的工程师，这篇都应该能给你一些可以立刻用上的东西。我会从最基础的原理讲起，带到标准代码的边界陷阱、四个经典变体、二分思想的扩展场景，再回到工程实践和面试考察点上，尽量把每一步背后的“为什么”也说清楚。

1. 二分查找的本质：为什么“折半”能跑赢“逐个找”

1.1 从猜数字游戏说起

小时候都玩过这样的游戏：对方心里想一个 1 到 100 之间的数字，你每次猜一个数，对方告诉你“大了”还是“小了”，直到猜中为止。如果老老实实从 1 猜到 100，运气好的话一次命中，运气不好要猜一百次。但如果每次都猜中间值——先猜 50，然后根据提示决定去 1~49 还是 51~100 继续折半——你会发现最多只需要猜七次。这就是二分查找最直观的感受：每次都能排除一半的错误答案，而不是排除一个。

这个策略的本质是：目标值所在的范围是确定的，每次比较都会把当前范围分成两半，其中一半可以彻底丢弃，因为有序性保证了目标值不可能出现在被丢弃的那一半里。这种“基于信息量做排除”的思路，和顺序遍历有本质区别。顺序遍历每次只排除一个元素，信息利用率极低；二分查找每次排除一半，信息利用率是指数级的。

1.2 时间复杂度到底怎么算

假设数组长度为 n，第一次查找后范围变成 n/2，第二次变成 n/2²，不断折半，直到范围缩小到只剩一个元素。这个过程需要经过 k 次折半，满足 n / 2^k = 1，解得 k = log₂n。所以二分查找的时间复杂度是O(log n)，空间复杂度是O(1)，因为我们只需要维护左右两个指针。

O(log n) 意味着什么？n = 1,000,000 时，log₂n 大约是 20；n = 10,000,000,000 时，log₂n 大约是 34。也就是说，即使数据量从一百万涨到一百亿，二分查找需要执行的比较次数只从 20 涨到 34。这种增长速度在算法领域属于极快的类别。作为对比，顺序查找的时间是 O(n)，数据量翻十倍，耗时也翻十倍；二分查找数据量翻十倍，耗时只是增加几次常数操作。

1.3 三个前提条件，缺一个都不成立

二分查找不是万能的，它有严格的适用前提，这一点在实际工程里特别容易被忽略。

第一个前提是数据必须有序。如果数组是无序的，折半就没有依据——你无法判断目标值应该去左半边还是右半边找。当然，不排序也有补救办法，比如先排序再查找，那是一套“排序 + 二分”的组合拳，代价是排序本身要 O(n log n)。如果只查一次，排序可能不划算；如果查很多次，排序一次、二分多次，收益就非常明显。这也是搜索引擎后台、数据库系统里常见的策略。

第二个前提是支持随机访问。二分查找需要直接跳到数组中间位置，这要求数据结构能在 O(1) 时间内按下标访问元素。数组和 vector 都满足，链表就不满足——链表定位中间节点需要从头遍历，每次折半的成本都是 O(n)，整体复杂度退化成 O(n log n)，还不如一次顺序遍历来得快。这也是为什么在链表上用二分查找很少见的原因。

第三个前提是存在单调性。二分不只适用于数组值的大小顺序，更通用的条件是问题的答案空间呈现单调特性——“满足某个条件”和“不满足条件”之间存在清晰的分界线。理解了这一点，才能理解后面要讲的“二分答案”思想为什么能在无穷多场景里发挥作用。

2. 标准二分查找的三种写法与边界陷阱

2.1 最经典的闭区间写法

先给出最常见的闭区间版本，C++ 风格的逻辑可以无缝迁移到其他语言：

int binarySearch(vector<int>& nums, int target) { int left = 0; int 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，因为当left == right时，区间里还有一个元素没检查。每次比较后，如果目标值在右侧，left = mid + 1，因为mid已经检查过了，不需要再保留在区间里；如果目标值在左侧，同理right = mid - 1。

闭区间写法是大多数人最早接触的版本，也是面试中最容易讲清楚的版本。它的循环不变量是：目标值如果存在，一定位于闭区间 [left, right] 中。每次迭代都在不破坏这个不变量的前提下缩小范围，这是二分查找正确性的核心依据。

2.2 左闭右开写法

另一个常见版本是左闭右开区间[left, right)，在 STL 和很多基础库里使用频率很高：

int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size(); 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; }

注意这里right初始值是nums.size()而不是nums.size() - 1，因为right表示的是“开区间”的右边界——它指向的范围不包含自身。循环条件也从left <= right变成left < right，因为当left == right时区间为空，已经没有任何元素需要搜索了。当目标值在左侧时，right = mid而不是mid - 1，因为已知mid不是目标值，但mid本身又不在[left, right)的范围内，可以让right直接收敛到mid。

这个写法的好处是：空区间直接返回，哨兵位置可以指向end()，在 C++ 的迭代器世界里非常自然。

2.3 三个版本之间的换算关系

把三种写法记住最好的方式是把它们当作同一个逻辑的三套“坐标系统”：

• 闭区间[l, r]：循环l <= r，左移r = mid - 1，右移l = mid + 1
• 左闭右开[l, r)：循环l < r，左移r = mid，右移l = mid + 1
• 开区间(l, r)：循环l + 1 < r，左移r = mid，右移l = mid

很多人在面试中写错，往往是因为三种写法混着用——一会儿用闭区间的循环条件，一会儿用左闭右开的边界更新。写之前先想清楚“当前区间到底包不包含右边界”，这个问题解决了，代码基本不会错。

2.4 一个必须避开的坑：整数溢出

mid的计算在经典教材里是(left + right) / 2，这在数值较小的时候没问题。但left + right可能超过 int 类型上限。在 Java 或 C++ 中，int 最大值是 2147483647，如果left和right都是接近上限的数，相加会出现整型溢出，得到负数，程序直接出错。

正确写法是：

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

这个公式的本质是把“从 left 开始再走一半的距离”作为中间下标，right - left最多不会超过数组长度，基本杜绝了溢出问题。这是我写二分时几乎形成肌肉记忆的一行代码，也建议你在实现时直接当成标准写法。

3. 二分查找的四个经典变体：从“找一个数”到“找一段区间”

基础版二分查找解决的是“找一个准确相等的目标值”。但真实世界里更常见的问题是：目标值可能不存在，或者存在多个，我需要的是第一个大于等于它的位置、最后一个小于等于它的位置。这些都可以通过二分查找在 O(log n) 时间内解决，关键是要理解变体的边界逻辑。

3.1 查找左边界：第一个不小于 target 的位置

这个操作在很多语言里就叫lower_bound，Python 的bisect_left也是同一个思路。它的返回值是：数组中最左边那个大于等于 target 的元素下标。

def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left

这个写法的关键点是：当nums[mid] < target时，说明mid以及它左边所有元素都比 target 小，可以全部排除，所以left = mid + 1；否则mid可能是第一个不小于 target 的位置，也可能在它左边还有更合适的位置，所以保留mid本身，right = mid。循环结束时，left == right，这个下标就是答案。如果所有元素都小于 target，返回len(nums)。

3.2 查找右边界：最后一个不大于 target 的位置

对称地，upper_bound在 C++ 里返回的是第一个大于 target 的位置，而“最后一个不大于 target 的位置”就是upper_bound - 1。直接用二分实现：

def upper_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 else: right = mid return left # 返回的是第一个大于 target 的位置

注意这里的条件换成了nums[mid] <= target：等于 target 时也把左边界右移，目的是跳过所有相等的元素。最终返回的位置是所有等于 target 的元素的下一个位置。想找最后一个等于 target 的位置，用upper_bound(nums, target) - 1即可。

3.3 左边界和右边界在排序数组中的应用

有了这两个操作，很多原本需要手写一堆逻辑的问题可以变成组合调用：

• 查找目标值是否存在于有序数组：lower_bound找到下标，检查下标不越界且值等于 target
• 统计 target 出现的次数：upper_bound - lower_bound，两个 O(log n) 操作，配合得行云流水
• 寻找插入位置：在有序数组中插入一个值并保持有序，下标就是lower_bound

在 C++ STL 里，这些功能早就封装好了，直接用std::lower_bound和std::upper_bound就行；Python 里用bisect模块，Java 里用Arrays.binarySearch的返回值做微妙处理。但面试的时候大概率会让你从零实现一遍，所以自己动手写出无 bug 版本是基本功。

3.4 左边界写法的统一模板

我给一个不容易记乱的统一模板，后续所有变体都可以基于它推导：

def binary_search_left(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if 条件成立: right = mid else: left = mid + 1 return left

对于 lower_bound，条件成立就是nums[mid] >= target；对于 upper_bound，条件成立是nums[mid] > target。如果你写的是“返回最后一个满足某条件的值”，只需要在 left 移动时记录候选答案，或者最后返回left - 1。这个模板把“找边界”问题统一成了“找第一个满足条件的位置”，条件由题意决定，区间的更新规则完全固定，特别适合用来推演不熟悉的二分变体题。

4. 二分思想“出圈”：从有序数组中扩展到更多场景

二分查找真正的强大，不只是在一个有序数组里找数字。它的思想可以泛化到任何“答案具有单调性”的问题上，这就是所谓的“二分答案”。热词里也有不少二分相关的搜索词，比如“二分查找pta函数”“算法流程图”，说明大家平时学的就是这些基础应用，但基础之上还有非常广阔的空间。

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

有一类问题正着做很复杂：求一个最优值，比如“数组分成 m 段之后，每段和的最大值最小是多少”。这类问题最好的入手方式不是直接找最优解，而是先写一个判定函数check(x)，回答“最大段和不超过 x 时，能不能把数组分成 m 段”。这个 check 函数在满足条件一边是 true、另一边是 false 时，答案空间天然具备单调性——x越大越容易满足。所以可以在 x 的取值范围上做二分查找，最终收敛到满足条件的最小值。

这种“对答案本身二分，不断调用判定函数”的模式，在编程竞赛和算法面试里出现频率极高。它和普通二分数组的区别是：二分对象从具体的数组元素变成了抽象的数值范围，判断依据从“值的大小比较”变成了“条件是否满足”。剩下的框架和标准二分完全一样。

4.2 求平方根：连续函数上的二分

一个经典例子是求非负整数 x 的整数平方根。LeetCode 上对应的题目是“x 的平方根”。思路是：在[0, x]范围内二分查找最大的 mid 满足mid * mid <= x。这本质上是右边界查询——找最后一个满足条件的位置。

def my_sqrt(x): left, right = 0, x + 1 while left < right: mid = left + (right - left) // 2 if mid * mid <= x: left = mid + 1 else: right = mid return left - 1

如果 x 很大，mid * mid可能溢出，要用mid <= x // mid来替代。这个例子很好地展示了二分的边界条件是如何被“条件成立”的具体含义驱动的。

4.3 浮点数二分：精度控制是关键

二分还可以用在连续实数域上。假设要求一个函数 f(x) 的零点，f 单调递增，且已知 f(0) < 0、f(10) > 0。这时可以不断折半区间，直到区间长度小于某个精度阈值，比如 1e-7，然后返回区间中点。

浮点数二分和整数二分最大的区别在于循环条件不再依赖left <= right，而是改为right - left > eps。eps的选择要结合问题精度要求：如果题目要求保留 6 位小数，eps取 1e-8 比较稳妥，防止舍入误差导致结果差一点。浮点数溢出的问题不再显著，但死循环风险依然存在——如果eps设得太小，远小于浮点数的机器精度，循环可能迟迟不结束。

4.4 旋转排序数组的二分

这也是算法面试高频题：一个原本有序的数组在某个位置发生了旋转，比如[4,5,6,7,0,1,2]，在其中查找目标值，要求 O(log n)。这个问题的核心思路是：mid 把数组分成一半，其中一半一定仍然有序。利用有序半边判断目标值是否在其中，然后决定去哪个方向继续二分。

def search_rotated(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[left] <= nums[mid]: # 左半边有序 if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: # 右半边有序 if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1

这个题考察的不只是二分模板，而是你能不能判断出“哪半边有序”，并且据此缩小搜索范围。理解了这层“逼近”思想，旋转数组、寻找旋转点、找到顶峰值这一类题都可以迎刃而解。

5. 工程实践：二分查找在生产环境中的真实身影

5.1 数据库索引内部的二分查找

数据库里的 B+ 树索引，内部每个节点存了一组有序的键值，查找某个 key 时，在节点内部用的就是二分查找来定位应当进入哪个子树或者命中哪个记录。一个层级内部只有几十到几百个键，二分是性价比极高的选择——每次查一个节点只要 O(log m) 次比较，m 是节点内的键数。

Redis 的跳表实现里，查找路径也借鉴了类似的思想：从高层往低层逐层逼近目标，每一层都尽量跳过足够多的元素。虽然跳表不是数组，但它用“有序 + 多层索引”复现了二分查找的跳跃感。理解二分的思想，能帮助你理解更多底层组件的设计。

5.2 标准库里被封装好的二分

绝大多数标准库都已经内置了二分查找，日常业务开发直接调用即可：

• Python：bisect模块，bisect_left和bisect_right是主力，注意排序列表才能用
• C++：std::binary_search只返回布尔值，std::lower_bound和std::upper_bound返回迭代器
• Java：Arrays.binarySearch查找成功返回下标，失败时返回-(insertion point) - 1的负数，用于推导插入位置

自己实现二分的能力更多体现在面试和特殊场景上，生产代码中不如直接调用久经考验的标准库实现，减少边界 bug 的概率。但前提是你要理解它们的行为——比如 Java 返回值怎么转成插入位置，bisect_left和bisect_right在重复元素时的区别，这些都是实际工程里会踩到的地方。

5.3 二分查找与排序、哈希的取舍

热词里出现了“排序算法”“数据结构与算法”，而且二分和排序经常成对出现。一个常见的工程套路是：数据频繁查询且对内存不敏感时，先一次性排序，然后每个查询走二分；如果数据量小，顺序遍历往往更简单直接，因为 CPU 缓存命中率高，常数项小，O(n) 未必输给 O(log n)。如果查询量极大且对精确匹配要求高，哈希表可能是更好的选择——用空间换时间，O(1) 的平均查询时间比二分更快，但代价是无法做范围查询、无法保持有序性。

二分查找的独特位置在于：它同时支持精确查找和范围查找，不占用额外内存，且元素越多优势越明显。如果你需要在有序数据上频繁做“找大于等于某个值的第一个元素”“统计区间内元素个数”，二分几乎没有替代方案。

5.4 大规模数据与外部查找

当数据量大到内存放不下时，二分就演变成了外部存储的查找策略。B+ 树之所以成为数据库索引的默认结构，正是因为它在磁盘上也保持了“每层近似二分”的特性，能够用很少的磁盘 I/O 定位到目标数据。理解这一点后，你会发现二分查找从内存数组到数据库再到分布式系统的扩展，是同一个思想在不同介质上的延续。

6. 算法面试考察点与常见 Bug 排查

6.1 面试官到底在考什么

算法工程师面试里，二分查找几乎是必考题。但它太简单了，简单到很多候选人掉以轻心。面试官通过这道题通常会考察三个维度：第一，边界条件是否考虑全面，空数组、一个元素、两个元素、重复元素是不是都能正确运行；第二，代码风格是否稳定，mid的计算方式、循环不变量的声明是否清晰；第三，能不能现场推导变体，比如让你写 lower_bound 然后改成 upper_bound，或者问“找峰值元素能不能用二分”。

我当面试官时见过不少候选人能背出模板，但是一旦我改变条件，比如改成“数组里有重复元素，找最左边的目标值”，就会卡壳。这说明他没理解二分搜索树上的“判断条件”是怎么随着题意变化的。我的建议是：不要只背模板，要把左边界、右边界、闭区间、开区间之间的换算关系练到条件反射。

6.2 高频 Bug 清单

第一个高频 bug 是死循环。典型场景：写左闭右开区间时，循环条件是left < right，但在else分支用了right = mid - 1，一旦目标值在左半边，区间更新后可能把 mid 排除掉了，但循环还能继续；更危险的是left = mid配合left < right在 left 和 right 相邻时会造成死循环——因为 mid 一直等于 left，left 无法前进。解决这个问题的方法是始终牢记：区间不变量要求每次循环结束时区间严格缩小，left = mid只有在循环条件为left + 1 < right时才安全。

第二个高频 bug 是边界外访问。初始化right = nums.size()后直接访问nums[right]会越界，尤其是在某些条件分支里。注意左闭右开区间里right是「哨兵」，不应该被读取。

第三个高频 bug 是重复元素处理不统一。找左边界和找右边界判断条件里的等号很容易写反——nums[mid] < target还是nums[mid] <= target决定了是跳过小于等于还是只跳过小于的元素。建议用 3.3 节给的模板来推导，不要在考场上临时想。

6.3 配套练习与刷题路径

想巩固二分查找，我推荐的练习路径是：

• 基础：在有序数组中查找目标值，练习闭区间和左闭右开两种写法
• 边界：实现lower_bound和upper_bound，处理重复元素
• 应用：搜索旋转排序数组、寻找峰值、求平方根、猜数字大小
• 进阶：二分答案题，比如“分割数组的最大值最小化”“爱吃香蕉的珂珂”“在 D 天内送达包裹的能力”
• 综合：二叉搜索树与二分思想结合，理解树形结构和数组二分的同构性

这个路径下来，二分相关的面试题基本都能覆盖。

6.4 调试二分的一个独门技巧

写二分容易出 bug 的时候，我建议把这个“全等于”问题当成一个纯函数来调试：首先固定使用左闭右开区间模板，把条件提取成单独的函数condition(mid)，让主循环只负责移动指针，不要在里面堆业务逻辑。这样调试时就能把一个复杂问题简化成“循环边界 + 判定函数”，问题立刻清楚很多。

我调试的时候还会故意测试这几个用例：空数组、单元素数组、target 比所有元素都小、target 比所有元素都大、target 恰好是第一个元素、恰好是最后一个元素、有大量重复元素。这七个用例跑一遍，99% 的边界 bug 都能暴露出来。这个习惯建议保留到正式开发中——凡是用到自定义二分的地方，先写这两个用例再上线。

7. 再补充一点：二分和二叉树的思想呼应

如果你学完了二分查找，不妨把目光放高一点去看数据结构与算法里其他相关内容。二叉搜索树本质上就是“二分查找的树形版本”。数组二分每次取中间节点，二叉搜索树则是把一个集合组织成一棵树，每个节点左子树的值都小于节点值，右子树的值都大于节点值，查找过程就是在树上每层决定向左还是向右。两者都是 O(log n) 的查找复杂度，区别只是数据组织方式不同。

热词里出现了“分治算法”和“归并排序算法”，归并排序就和二分有着天然的联系——分治的第一步就是“把数组从中间切开”，递归处理左右两半，再合并结果。很多算法都是从二分这种“一刀切两半”的思维方式延伸出去的。理解了二分的思维方式，后续学归并排序、快速排序、二叉平衡树、线段树都会顺畅很多。

我个人在实际写代码时，还有一个很深的体会：二分查找看似简单，但它是那种“会者不难，难者不会”的算法。它考察的是你对区间不变量的理解、对问题单调性的敏感度，以及动手前想清楚边界的习惯。建议把本文的模板抄下来，自己手写三遍——第一遍看着写，第二遍合上代码自己写，第三遍换一种区间写法试试。写完这三个版本之后，遇到任何二分变体题，你都会觉得“换汤不换药”。

最后分享一个小技巧：做题时如果实在不确定边界条件，可以在纸上把一个长度为 5 的数组完整跑一遍这个流程，手动模拟每一步的 left、right、mid 变化。我面试和带新人的时候，发现不少人靠这一步就能自己找到 bug 所在。二分查找要真正成为肌肉记忆，靠的就是这种反复的“手动追踪”。