企业官网建设流程全解析

我想从一个面试场景说起。面试官递过一个数组：[4,5,6,7,0,1,2]，问我“这个数组是乱序的，还能用二分查找吗”。我当时脑子里全是“二分的前提是有序数组”，差点直接答“不能”。可自己笔画了两下就发现，这数组虽然整体无序，但它是两段递增序列拼起来的，最小值恰好卡在拼接处，用二分完全能找出来。后来我才明白一个关键道理：二分查找真正依赖的从来不是单调性，而是序列具备某种“二段性”。这也是这篇文章想讲清楚的东西——什么是二段性，怎么用二段性在非单调序列上寻找极值，以及我在实际调试中踩过的各种边界坑。如果你想进阶二分查找，看过很多模板却总在变形题上卡住，这篇文章应该能帮你把底层逻辑理顺。

1. 有序才能二分？真正的前提是“答案可以被某条性质一分为二”

1.1 从一次面试翻车说起

先回到那个面试场景。当我意识到旋转数组也能二分时，第一个反应是去翻各种“二分变种模板”，结果越看越乱：有找第一个大于 target 的模板，有找最后一个小于 target 的模板，有左闭右开区间模板，还有左闭右闭区间模板……每个模板都配着自己的边界条件，背下来不难，可一旦题目换了个形状，我又开始怀疑“这个能不能二分行不行”。

踩的次数多了，我开始总结经验：我们这些做题的人之所以频繁翻车，是因为把“数组有序”当成了二分的充分条件。实际上，只要你能找到一个布尔性质，让它在序列上“一分为二”——左边全是一种状态，右边全是另一种状态——那二分就能工作。这个思想比“有序”二字强大得多，它才是我后来解决一堆极值问题的真正钥匙。

1.2 二段性的定义

给个严谨但不拗口的定义：如果一个区间[l, r]存在一个分界点k，使得某个布尔性质P在[l, k-1]上恒为某种取值，在[k, r]上恒为另一种取值，那么这个区间对性质P就具备二段性。

听起来有点抽象，我拿升序数组举例。数组[1, 3, 5, 7, 9]是单调的，定义性质P(i) = arr[i] >= 5，那么从左往右取到的布尔序列是F, F, T, T, T。分界点就是第一个满足P的位置，也就是数值5所在的下标。你发现没有：单调性只是二段性的一个特例，一个升序数组天然能产生这种“前假后真”的二段结构。

那旋转数组呢？[4,5,6,7,0,1,2]以最小值0为分界，左侧[4,5,6,7]中每个元素都大于最后一个元素2，右侧[0,1,2]中每个元素都小于等于2。所以如果定义性质P(i) = arr[i] > arr[r]，那么从左往右 P 的取值是T, T, T, T, F, F, F——同样是典型的两段结构。序列虽然没有全局单调性，但这个布尔性质却已经“一分为二”了。

1.3 为什么“找极值”也能套二分

再看寻找极值的问题。假设给定一个“山脉数组”[1,3,5,4,2]，峰值是5，它本身并不满足“大于某个固定值”这类普通性质，但它可以换成相邻关系的视角：定义P(i) = arr[i] < arr[i+1]，意思是“当前位置还在上升段”。在峰值之前，这个值恒为True；在峰值之后，这个值恒为False。于是序列的 P 取值是T, T, F, F，分界点就是峰值。

所以“找极值”和“找 target”本质上完全一致，都是夹逼分界点。区别只在于：找 target 时我们比较的是“mid 和某个固定值”，而找极值时我们比较的是“mid 和它的邻居”。这个视角切换，是我能把这堆题目统一理解的关键，后面所有模板都围绕它展开。

2. 把二段性翻译成二分查找：一套可复用的判断框架

2.1 从“找值”模板到“找分界点”模板

传统二分模板长这样：“mid 大了就往左，mid 小了就往右”，核心是比较大小。而二段性模板写的不是“大小”，而是“性质取真还是取假”。我给你一个可以直接套的框架：

def binary_search_segment(nums): l, r = 0, len(nums) - 1 while l < r: mid = l + (r - l) // 2 if segment_property(nums, mid): # 你自己定义的性质 l = mid + 1 # 分界点在右侧 else: r = mid # 分界点在左侧（含mid） return l

真正需要动脑子的只有一个segment_property。其余部分几乎原封不动。当循环结束时，l == r，这个位置往往就是分界点，也就是我们要找的极值所在位置。这套模板我写了不下二十道题，每次只需要替换segment_property内部的一两行比较逻辑。

2.2 设计“收敛方向”的三步法

三步法看着简单，但每一步都有讲究：

1. 定义性质 P：这个性质必须和答案的“分界”强绑定。找极值的话，性质通常是“mid 位于极值的哪一侧”。旋转数组里用的是“是否大于最后一个元素”，山脉数组里用的是“是否处于上升段”。
2. 判断 mid 处 P 的取值：取值为真时，说明当前位置在分界点的这一侧，我们判断目标在另一侧；取值为假时，说明当前位置在另一侧，目标可能就在当前位置或其更左的位置。
3. 收缩区间：每次收缩都必须保证目标点仍然留在新区间里，绝不能把它丢出去。

我给个实际例子。旋转数组里，nums[mid] > nums[r]为真，说明 mid 落在左边那段递增序列里，最小值一定在 mid 的右边，所以l = mid + 1。反之，说明 mid 已经落在右边的最小值区域附近，最小值在 mid 左侧或就是 mid，所以r = mid。这样一个循环下来，区间始终围着最小值收拢。

2.3 河流石块类比

为了让自己记忆更牢，我喜欢用一个“河流石块”的类比。想象一条河中间立着一块石头，河水被石头分成两段，一段向左流、一段向右流。你可以在任意位置测试“这里的水朝哪个方向流”，然后用二分不断缩小区间，最终就能定位到石头所在位置。石头就是分界点（极值），水流方向就是那条布尔性质。

这个类比说明了两个重要前提：第一，性质必须在分界点的两侧“状态不同”，否则没法用；第二，每次测试必须是便宜的，一次比较交互就能得到结果。满足这两点，二分的对数时间复杂度才有意义。我每次分析一道新题时，都会先问自己：这道题的“石头”是什么，“水流方向”的性质是什么。想明白这两点，模板基本就出来了。

3. 旋转数组找最小值、山脉数组找峰值与“答案值域”的二分

3.1 旋转有序数组找最小值

这是二段性最经典的落地题目。给定一个原本升序的数组，把它在某个未知位置旋转，比如[4,5,6,7,0,1,2]，要求找到最小值。完整代码如下：

def find_min(nums): l, r = 0, len(nums) - 1 while l < r: mid = l + (r - l) // 2 if nums[mid] > nums[r]: l = mid + 1 else: r = mid return nums[l]

几个关键点值得展开：

• 为什么和nums[r]比较，而不是nums[0]？因为nums[0]在数组没有旋转时就是最小值，在旋转后可能反而是右侧序列中偏大的值，选择它会干扰判断。以最后一个元素作为锚点，可以统一处理“旋转了 0 次”和“旋转了若干次”两种情况。
• 为什么nums[mid] > nums[r]时移动l？当 mid 位于左段，说明右段元素整体比 left-segment 的元素小，最小值还没越过 mid，只能向右找。
• 循环次数是 O(log n)，因为每次区间直接砍半。

手动走一遍[4,5,6,7,0,1,2]：l=0, r=6, mid=3，nums[3]=7 > nums[6]=2，所以 l=4；然后 l=4, r=6, mid=5，nums[5]=1 > nums[6]=2为假，于是 r=5；再走一轮 l=4, r=5, mid=4，nums[4]=0 > nums[5]=1为假，r=4，循环结束，nums[4]=0就是答案。整个过程每次只需要一次比较，非常干净。

3.2 山脉数组找峰值

山脉数组是另一种极值问题的标准形态。它先严格递增、再严格递减，且相邻元素不相等，要求找出峰值所在下标。常见写法：

def peak_index(arr): l, r = 0, len(arr) - 1 while l < r: mid = l + (r - l) // 2 if arr[mid] < arr[mid + 1]: l = mid + 1 else: r = mid return l

这里arr[mid] < arr[mid + 1]就是在判断“mid 是否还处于上升段”。如果是，峰值一定在 mid 的右边，所以l = mid + 1；如果不是，说明 mid 已经在下降段，而峰值要么是 mid 本身，要么在 mid 左边，所以r = mid。注意此处是r = mid，不是r = mid - 1，因为arr[mid]完全可能是峰值。

拿数组[0, 2, 1, 0]来走一遍：l=0, r=3, mid=1，arr[1]=2 < arr[2]=1为假，所以 r=1；然后 l=0, r=1, mid=0，arr[0]=0 < arr[1]=2为真，所以 l=1；循环结束，答案就是下标 1，即峰值2。如果遇到这种只靠相邻比较就能解决问题的题，它的核心就是“用走势判断方向”。

3.3 从“数组上的极值”扩展到“答案值域上的二段性”

二段性不只在数组元素上出现，还大量出现在“答案值域”上。很多优化类问题，比如“最小化最大值”“最大化最小值”，判断某个候选答案是否可行时，可行性的取值在值域上往往也是True, True, ..., False, False或反过来的二段结构。这时我们对“答案”本身做二分，每次用feasible(mid)判断能否满足，根据结果决定往哪个方向逼近。

这类题的标志是：题目要求输出一个整数答案，而这个答案的范围通常很大（比如0到10^9），没法线性枚举。你只需要一个判定函数feasible(x)，它告诉你x是否可行，然后原封不动套用二分的那个框架，只是把原来的“性质判断”换成了“可行性判断”。所以二段性的真正威力在于：它让你从“容器有序”的思维里跳出来，转向“答案可行域分段”的思维。一旦建立这个视角，很多看着不需要二分的题，最后都能用二分解掉。

4. 边界与死循环：我用二段性二分时踩过的坑

4.1 mid 取整方向决定是否死循环

二段性二分最容易翻车的地方，不是性质选错，而是 mid 的取整方向。很多新手写完之后发现“程序卡死了”，十有八九是下面这种写法：

l, r = 0, 1 mid = (0 + 1) // 2 # 结果是0 # 如果某个条件成立，执行 l = mid，此时 l 仍然是0 # 下一次循环 l=0, r=1, mid=0，永远重复

为什么会这样？因为mid = (l + r) // 2是向下取整。当区间只剩两个元素时，mid 会停在左边界。如果这时你写的是l = mid，那 l 根本不会前进，死循环随之而来。解决办法有两个：要么把更新写成l = mid + 1，这样即使 mid 停在下边界也不会卡住；要么把取整方式改成向上取整mid = (l + r + 1) // 2，这样 mid 会停在上边界，配合l = mid就不会死循环。这两种方案只能二选一，混用必出问题。

4.2 while l < r 结束时，l 就是答案而非“答案旁边”

另一个常见误解是：循环结束后，还担心l不是答案，非要去检查l-1或l+1。我一开始也这样，结果多做几步检查反而把边界算错。在“找分界点”这个模板里，循环不变量保证了：区间[l, r]始终包含目标分界点，而while l < r结束时l == r，意味着这个位置就是分界点本身。

用前面的旋转数组代码来看，循环结束后直接返回nums[l]就是最小值；山脉数组直接返回l就是峰值下标。不需要再判断l和l+1谁更大。如果你觉得不放心，可以在考试或面试现场用两个元素的极简数组手动模拟一遍，大多数情况下一轮就收缩掉了。

为了便于记忆和排查，我列一个常用模板对照表：

4.3 重复值、退化场景和复杂度的变化

二段性二分并非万能，遇到重复值或退化数据时要特别小心：

• 旋转数组有重复元素：[1,1,1,1,1,0,1]这类输入中，nums[mid] == nums[r]时我们没法判断 mid 到底在哪一段，只能保守地r -= 1。这样做保证了正确性，但最坏情况下每次只缩一个位置，复杂度退化到 O(n)，不再是严格的 O(log n)。
• 山脉数组相邻元素相等：比如[1,2,2,1]，arr[mid] < arr[mid+1]的判断会变得不可靠，二段性被破坏。这种情况下老老实实用线性扫描找峰值，别硬套二分。
• 数组长度为 0 或 1：写函数前先判空，长度为 1 时直接返回下标 0。不要指望二分模板自己处理这种极端输入。

真实场景中，重复值问题非常常见。我建议把“无重复”和“有重复”两段模板分开背，前者是严格 O(log n)，后者是退化版，都需要知道为什么能跑对。

4.4 调试与验证：暴力解是二分最好的磨刀石

最后分享一个我调试二分题目的固定做法：写一个暴力解法作为对照。比如旋转数组最小值题，我先写一个min(nums)的线性解法，再随机生成长度 1 到 20、元素随机的数组，把随机数组喂给二分函数和暴力函数，对比结果。跑几千几万次，只要有一次不一致，立刻就能复现并定位问题。

这个方法听起来朴素，但特别有效。因为二分的错误往往只出现在极小边界或特定数组形状上，光靠肉眼很难看出来。用随机数据暴力对拍，能非常快地暴露“收敛方向判断错误”或“越界访问”这类问题。你甚至可以写一个小脚本：

import random def brute(nums): return min(nums) for _ in range(10000): n = random.randint(1, 20) base = sorted(random.sample(range(0, 50), n)) k = random.randint(0, n - 1) arr = base[k:] + base[:k] if find_min(arr) != brute(arr): print("error at:", arr) break

跑一轮下来，如果全程没报错，你对自己的二分实现才真正有了信心。我个人的体会是，一个人把二段性二分用得熟不熟，并不只看他能不能写出标准模板，而是看他能不能快速给任意题目定义一个“会翻转的性质”。一旦你习惯用“分界点”的视角看问题，很多原本看起来毫无规律可言的序列，都会被慢慢夹逼出来。这个过程没有太多捷径，多画图、多写暴力对拍，手感自然就出来了。