企业官网建设流程全解析

如果让你在一本一千页的字典里查一个字，你会从第一页开始翻吗？正常人不会，你会直接翻到大概的位置，然后根据页码大小往前或往后跳。二分查找干的就是这件事——只不过它把“大概的位置”变成了“每次都精确地砍掉一半”，然后在一个有序数组里用 O(log n) 的时间找到目标元素。

我第一次学二分查找的时候，觉得这玩意儿简单得不像算法：不就是猜数字游戏嘛。后来刷题、面试、写工程代码，才发现自己在这上面翻车的次数比想象中多得多。边界条件写错、死循环、返回位置偏一个、区间开闭搞混……每一个坑都真实存在。这篇文章把我这些年对二分查找的理解、踩过的坑、以及怎么写不容易错的经验全部整理出来，不管是刚学算法的初学者，还是准备面试的选手，或者写代码时偶尔需要手写二分的老手，都能从这里拿到可以直接用的东西。

1. 二分查找到底在解决什么问题

1.1 从猜数字游戏说起：为什么每次都能排除一半

想象一个场景：对方在心里想了一个 1 到 100 之间的数字，你每次猜一个数，对方告诉你“大了”还是“小了”，保证在 7 次以内猜中。为什么是 7 次？因为 2^6 = 64 < 100 ≤ 128 = 2^7，每次猜中间数，最多 7 次就能把范围缩到只剩一个数。

二分查找的本质就是这个过程。给定一个有序数组和一个目标值，每次取当前区间的中点，比较中点值和目标值的大小关系：相等就找到了；中点值比目标值小，说明目标只可能在右半部分，于是把左边界移动到中点右侧；中点值比目标值大，说明目标在左半部分，把右边界移动到中点左侧。每比较一次，搜索区间缩短一半，这就是“二分”二字的由来。

这个过程用大白话描述就是：每次都在“当前可能包含答案的那一段”里继续猜，而不是从头到尾一个个试。它和暴力遍历最本质的区别在于，暴力遍历每次只能排除一个元素，而二分查找每次能排除一半元素。这个差异在数据量小的时候看不出来，一旦数据量上了百万、千万级别，差距就是天壤之别。

1.2 有序是第一前提：O(log n) 从哪来

很多人问，二分查找这么好用，为什么不把所有查找都改成二分？答案是：二分查找有个硬性前提——数据必须有序。如果数组是无序的，你取中点比较之后，根本不知道目标值该往哪边找，因为中点左边可能有比它大的，右边也可能有比它小的，任何判断都是无效的。

所以使用二分查找之前，第一件事就是确认数据有序。如果数据本身无序，要先排序，排序本身要付出 O(n log n) 的代价，这就得权衡了：是一次性排序后反复查询划算，还是直接线性扫描更划算。实际工程里，如果你需要频繁在一个固定数据集上查找，排序一次、查询多次，用二分就非常划算；如果数据一直在变、只是偶尔查一次，那维护有序性的成本可能比查找本身还高。

另外还有一个隐含前提容易被忽视：数据结构必须支持随机访问。数组可以通过下标 O(1) 取到任意位置的元素，所以二分查找在数组上非常自然。但如果数据存在链表里，你要取中点就得从头遍历，每次找中点都要 O(n)，那二分查找的总复杂度会退化到 O(n log n)，毫无优势可言。这也是为什么实际项目中，凡是需要快速二分查找的数据结构，底层几乎都是连续内存的存储。

1.3 复杂度计算：二分查找到底快在哪

假设数组长度为 n，第一次查找后区间长度变成 n/2，第二次变成 n/4，第三次变成 n/8……经过 k 次查找后，区间长度是 n / 2^k。当区间长度缩小到 1 时，肯定能确定答案，所以最坏情况下需要查找的次数 k 满足：

n / 2^k = 1 → k = log2(n)

所以二分查找的时间复杂度是 O(log n)，而顺序查找是 O(n)。空间复杂度方面，迭代写法只需要几个变量存边界和中间值，是 O(1)；递归写法每次调用会占用栈空间，复杂度是 O(log n)，但因为递归深度一般不超过几十层，实际影响也不大。

举个例子直观感受一下：一个 10 亿个元素的数组，顺序查找最坏要比较 10 亿次，而二分查找最多只需要比较 30 次。这就是从“逐个排查”到“按规律跳查”的降维打击，也是为什么二分查找能成为一个基础到不能再基础、却又重要到不能再重要的算法。

2. 二分查找的两种典型实现写法

2.1 闭区间写法：最容易理解和记忆

理解二分查找最直观的方式是定义闭区间 [left, right]，表示目标值可能存在的范围包含 left 和 right 两个端点。初始化时 left = 0，right = n - 1，循环条件为 while (left <= right)，因为当 left 等于 right 时，区间里还有一个元素，必须继续判断。

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

这段代码我建议每个学二分查找的人先背下来。它的核心逻辑是：每次比较完 nums[mid] 和 target 之后，如果 nums[mid] 不是答案，就把 mid 排除出搜索范围，所以 left 更新为 mid + 1，或者 right 更新为 mid - 1。

用 C 语言写也是一样的逻辑：

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

我用具体的例子走一遍：nums = [1, 3, 5, 7, 9]，target = 5。初始 left = 0，right = 4，mid = 2，nums[2] = 5，直接命中返回 2。如果 target = 8，mid = 2 时 nums[2] = 5 < 8，left 变成 3；新一轮 mid = 3，nums[3] = 7 < 8，left 变成 4；再一轮 mid = 4，nums[4] = 9 > 8，right 变成 3。此时 left = 4，right = 3，left > right，循环退出，返回 -1。整个流程非常清晰，配合图画一遍就懂了。

2.2 左闭右开写法：工程实践和标准库的默认风格

如果去读 C++ 标准库或 Java 的工具类源码，你会发现它们更偏爱左闭右开区间 [left, right)，也就是 left 包含在范围内，right 不包含。这种风格在编程语言里有广泛共识：迭代器的 begin 和 end、Python 的 range、数组切片都是左闭右开，好处是区间长度直接用 right - left 计算，而且空区间自然表示为 left == right。

def binary_search(nums, target): left, right = 0, len(nums) # [left, right) while left < right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 # 目标在右半边，mid已排除，所以left = mid + 1 else: right = mid # 目标在左半边，mid已排除，但因right不包含，直接right = mid return -1

注意这里的关键差异：闭区间写法里 right = mid - 1，而左闭右开写法里 right = mid。原因在于 right 本身指向的元素不在搜索范围内，所以把 right 更新为 mid，等价于把 mid 及其右侧元素全部排除。循环退出条件是 left < right，因为当 left == right 时区间已经为空。

这两种写法没有绝对的好与坏，但左闭右开的好处是更贴近标准库风格，在做变体题目时语义更统一。我的建议是把两种写法都掌握，但日常手写时用自己最熟悉的那一种，关键是脑子里要清楚当前区间到底包不包含 right。

2.3 递归写法：能看懂，但不推荐

递归版本在逻辑上更简洁，但工程上我并不推荐，因为递归有函数调用开销，而且深度受限——虽然 log2(n) 对于正常数据量不会爆栈，但完全可以用迭代写，没必要引入额外开销。递归写法了解一下即可：

def binary_search_recursive(nums, target, left, right): if left > right: return -1 mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: return binary_search_recursive(nums, target, mid + 1, right) else: return binary_search_recursive(nums, target, left, mid - 1)

这段代码的思路和闭区间迭代完全一致，只是在区间为空时返回 -1。递归写法比较适合展示“分治”思想，写算法题时能帮助理解，但实际项目里我建议一律用迭代，因为迭代版没有栈溢出的风险，性能也更好。

3. 边界条件与循环不变量：最容易翻车的三道坎

3.1 死循环是怎么产生的

二分查找最常见的翻车现场就是死循环。症状表现为程序卡住不返回，或者运行时明显超时。死循环的根源只有一个：区间没有在每一轮循环中严格缩小，导致某一轮区间大小不变。

最典型的情况是在查找右边界或使用左闭右闭写法时，把 left 更新成了 mid 而不是 mid + 1。比如在区间 [left, right] 闭区间中，如果 left = mid，当 left 和 right 相邻时，即 right = left + 1，mid = left + (right - left) // 2 = left，如果这时候判断 nums[mid] < target，把 left = mid，那么 left 根本没变，下一轮还是同样的 left 和 right，形成死循环。

怎么从根上避免？核心是理解循环不变量：每一轮循环开始时，你要找的目标一定在 [left, right] 区间内（或者 [left, right) 区间内），而每次更新 left 或 right 时，必须保证目标仍然落在新区间里，且区间大小严格减一。

你可以用一个很简单的检查方法：把循环里每一种分支都走一遍，确认区间长度的变化。闭区间写法，如果 left = mid，那么当区间长度为 1 时，mid == left，更新后区间不变，死循环；如果改成 left = mid + 1，区间长度为 1 时 left 增大，区间变空，循环退出。同理右边界更新，闭区间要用 right = mid - 1，左开区间要用 right = mid，都要确认区间必然缩小。

3.2 经典溢出问题：left + right 可能越界

另一个容易出问题的点，是计算中间值的时候直接写 mid = (left + right) / 2。在大多数现代编程语言中，int 是 32 位有符号整数，最大值是 2147483647。如果 left 和 right 都接近这个上限，left + right 就可能溢出变成负数，mid 算出来就是个负数，程序直接乱套。

解决方法是写成 mid = left + (right - left) / 2，这一步在数学上完全等价于 (left + right) / 2，但因为先做了减法，left 和 right 的差一定不会超过 right 的值，所以不会溢出。这是工程上写二分查找的基本功，面试时写 mid = (left + right) // 2 一般面试官不会说什么，但写 mid = left + (right - left) // 2 会给人留下更严谨的印象。

如果你追求极致性能，还可以用位运算写法 mid = left + ((right - left) >> 1)，右移一位相当于除以 2。不过现代编译器基本都会把除以 2 优化成移位，所以可读性优先写除法或 // 就可以了。

3.3 变体问题：查找第一个等于目标值的元素

基础二分查找能找到一个等于目标值的元素，但如果数组里有重复元素，要求返回第一个等于目标值的下标，或者最后一个等于目标值的下标，标准的二分查找就不够用了。这是面试里特别爱考的变体题，也是实际业务里很常见的需求。

先讲思路：找第一个等于目标值的位置，核心转变是，找到等于目标值的元素后，不直接返回，而是继续把右边界往左压，因为“第一个等于”一定在更左边。代码用左闭右开区间写会非常干净：

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

这个函数返回的是第一个大于等于 target 的位置。如果 target 存在，它返回的就是第一个等于 target 的下标；如果 target 不存在，它返回的是 target 应该插入的位置。类似的，查找最后一个小于等于 target 的元素位置，可以对称写出来。

为什么这种写法不容易出错？因为它的循环不变量非常清晰：left 之前的所有元素都严格小于 target，right 及其之后的所有元素都大于等于 target，循环结束时 left == right，就是第一个大于等于 target 的位置。每次比较都严格推进区间，不会死循环，也不用纠结边界。掌握了这种“约束上界”和“约束下界”的思想，二分查找的各种变体都可以很快推出来。

4. 二分查找不止用在数组里：实战场景延伸

4.1 在答案空间上二分：经典“二分答案”

二分查找最妙的应用场景，是对答案本身进行二分，通常称为“二分答案”。它的适用场景是：你要求一个最值，但这个最值不好直接计算，却可以用一个判断函数 f(x) 来回答“当答案是 x 的时候是否可行”。如果 f(x) 具有单调性——即 x 越大越难满足，或者 x 越大越容易满足——你就可以在答案的可能范围里二分搜索。

举个例子：把一根长 10 米的木头切成若干段，要求每段长度都是整数厘米，至少要切出 k 段，问每段最长能有多长。如果你从 1 厘米开始一个个试到 1000 厘米，效率低；正确答案是二分答案：假设每段长 L 厘米，能切出的段数是 floor(10 / L)，如果大于等于 k，说明 L 可以更大，否则 L 必须更小。因为我切的段数和 L 是单调关系，所以直接二分搜索 L，很快就能找到最大值。

再比如求平方根的问题：给定 x，求 sqrt(x) 的近似值。你可以在 [0, x] 区间里二分数值 mid，判断 mid * mid 是否大于 x，大于就往左找，小于就往右找。这种“把求解问题转换为判断问题”的思路，是二分查找从数据结构算法升级为通用算法思想的关键一步，很多竞赛题和工程优化问题都靠它。

4.2 浮点数二分与精度控制

二分查找在实数域上和整数域略有不同。整数域的循环退出条件是区间为空或者 left > right，而实数域因为无法精确枚举，通常用区间长度小于某个精度值 eps 作为退出条件：

def sqrt_binary(x, eps=1e-7): left, right = 0.0, x while right - left > eps: mid = left + (right - left) / 2 if mid * mid > x: right = mid else: left = mid return left

注意浮点二分的更新方式，因为实数没有“下一个”的概念，所以 left = mid 和 right = mid 都不会导致死循环，只要区间长度还在持续缩小。eps 的选取也很有讲究，如果直接用 1e-7 做循环条件，在数据规模大的时候可能要循环几十次，而且浮点误差可能在接近 eps 时干扰判断。更稳妥的写法是固定循环次数，比如 60 次或 100 次，因为每循环一次区间缩小一半，60 次已经能将区间缩到原来的 2^-60，远超任何常见精度需求。

实际上工程里求平方根基本会调用标准库的 sqrt，根本不需要自己写。但浮点二分的思路在数值计算中很常见，比如求解方程、拟合参数、机器学习里的学习率搜索简化版等，所以掌握它的精度控制方式还是有价值的。

4.3 旋转数组查找、查找峰值等进阶变体

再往深走一步，二分查找还可以用在数组本身不是完整有序的场景。经典的旋转排序数组问题：数组 [4, 5, 6, 7, 0, 1, 2] 是在有序数组上旋转得到的，要在这个数组里查找 target。

思路是：每次取中点后，数组被分为两半，其中至少有一半是有序的。先判断左半边 nums[left] 到 nums[mid] 是否有序：如果有序，而且 target 在这个范围内，就收缩到左半边；否则去右半边。如果左半边无序，说明右半边有序，用同样的逻辑判断。虽然数组全局不是有序的，但每次判断都可以确定目标在哪一半，所以依然可以用 O(log n) 解决。

查找峰值则是另一种应用：在一个相邻元素不相等的数组中，找到一个比左右邻居都大的元素。即使数组整体无序，你仍然可以用二分，因为“往上坡方向走”一定能找到峰值。这种“根据局部单调性决定搜索方向”的思路，是二分查找在无序数据上也能生效的经典案例。

这些变体题的价值在于锻炼一个能力：看到问题后判断出“能不能二分”“往哪个方向二分”。判断的核心始终是单调性——如果每次排除一半之后，答案一定在剩下的那半边里，就能用二分。

5. 常见问题与排查技巧实录

5.1 一份二分查找的排错检查清单

我把自己这些年写二分踩过的坑整理成了一张速查表，每次代码出问题就对着查，基本都能定位。

每次写完二分，先把空数组、单元素数组、两个相同元素数组、目标值在最左、最右这几组用例跑一遍，基本能覆盖大多数边界问题。这个习惯我一直保留到现在，虽然大多数时候用标准库，但手写时宁肯多花 30 秒多测几个用例，也比上线后出 bug 好。

5.2 面试和工程场景里的实用性提醒

面试算法题时，二分查找看似简单，但越简单越容易暴露基本功。我面试别人的时候，最看重的不是写出了几行代码，而是候选人能不能准确描述循环不变量：他设计的 left 和 right 分别代表什么、开区间还是闭区间、为什么 while 条件是 <= 还是 <、更新时要不要加减 1。这些问题全答清楚了，代码基本不会错；答不清楚，代码可能会“侥幸跑通”，但一改边界用例就原形毕露。

工程实践中，我建议能调标准库就调标准库。C++ 里有 std::lower_bound 和 std::upper_bound，Java 里有 Arrays.binarySearch，Python 里有 bisect 模块，这些标准实现都经过了海量测试，边界行为非常严谨。但在调用之前你仍然要知道它们的行为约定，比如 Python 的 bisect_left 返回的是插入点而不是目标下标，C++ 的 lower_bound 要求区间是左闭右开，用错了照样出问题。原理搞明白了，用标准库才用得放心。

5.3 产品代码里如何选择二分还是哈希

很多人会问：既然查找速度都追求最快，为什么不用哈希表，用二分是不是落伍了？答案是场景不同。哈希表查找是 O(1) 平均复杂度，但它的代价是内存占用高，而且无序、无法做范围查询。如果你需要按区间查找数据，比如“找出所有价格在 100 到 200 之间的商品”，哈希表毫无办法，有序数据结构加二分才是正解。有些场景对数据有序性有硬性要求，比如数据库索引的 B+ 树查找，底层思想就是有序结构上的区间查找。

我在实际项目里处理过一批千万级别的配置数据，需要按 key 查找，还经常需要做范围遍历，最后选择了有序数组加二分。内存占用比哈希表小很多，查询耗时稳定在几百纳秒级别，而且范围查询直接定位到起始下标然后顺序遍历前几个元素就行，整体效果非常理想。这个选择背后的核心判断就是：查什么、怎么查、数据长什么样，决定了用什么算法。

最后分享一个我调试二分查找的笨办法：如果代码死活不对，别硬想，在循环里把 left、right、mid 都打印出来，跑一两组用例看变化轨迹。你会发现要么是某一步 left 没变导致死循环，要么是更新方向反了导致漏掉答案。把这三个值的变化过程看清楚，比盯着代码猜一百遍都有用。二分查找这个算法，看起来只有十几行，但它教会我的却是“每次决策必须建立在可证明的区间不变量上”这一条思维习惯，这种习惯在复杂系统设计里同样极其有用。