入门：二分的广义化与三变体速览
基于通用算法概念 · 核于 2026-07
速查
- 二分的广义本质：不止「有序数组查值」——只要存在一个判定
check(x)关于x单调（x增大时判定结果只朝一个方向变化，如从「可行」单调变「不可行」），就能对x二分。单调性 ⇒ 可二分。 - 朴素二分（复习）：对下标二分，
nums[mid]与target比较，每次把区间砍半，O(log n)。前提是nums整体有序。 - 变体一·旋转数组搜索：整体被旋转（如
[4,5,6,7,0,1,2]），但拆成两段后各自有序。二分时判断mid落在哪段、哪半边有序，仍能每轮排除一半，O(log n)。 - 变体二·二分答案：对答案值域（而非下标）二分。取候选答案
mid，调用check(mid)判断是否可行，靠「可行性关于答案单调」折半值域。复杂度 O(log(值域) × 复杂度(check))。 - 变体三·三分法（Ternary Search）：目标函数
f单峰（先增后减）或单谷时，取m1 < m2两内分点，比较f(m1)与f(m2)，每次排除左或右三分之一的区间，逼近极值，O(log n)（底数 1.5）。 - 三变体的共性：都依赖广义单调性——旋转数组靠「部分有序」保证每轮能排除一半；二分答案靠「可行性单调」保证能折半值域；三分靠「凸性」保证能排除一侧。
- 旋转数组搜索要点：判断
mid在左段还是右段（nums[lo] <= nums[mid]则左段有序），再判断目标落不落在这段有序的半边，决定收lo还是hi。 - 找旋转点 = 找最小值：旋转后最小值位置即「断点」。
nums[mid]与nums[hi]比较：nums[mid] > nums[hi]最小在右半，否则在左半。 - 含重复元素退化：
nums[mid] == nums[lo]（或== nums[hi]）时无法判断哪段有序，只能lo++逐个排除，最坏 O(n)。 - 二分答案适用条件：①答案有上下界；②
check可在多项式时间完成；③「可行性」关于答案单调（答案越大越难满足，或越小越难）。 - 二分答案经典题型：「最大化最小值」「最小化最大值」「第 k 小」——如「分裂数组最大值最小化」「木头切割最少得 k 段」「吃香蕉速度」。
- 三分要点：单峰时
f(m1) < f(m2)⇒ 极值在m1右侧（排除[lo, m1]），反之排除[m2, hi]；浮点场景要设精度eps与足够迭代次数。 - 三分 vs 二分：二分要「有序离散/可枚举」，三分要「连续凸函数」——多峰或非凸函数三分会陷入局部极值，不适用。
- 进阶顺序：旋转数组搜索 → 二分答案与三分法 → 参考。
一、为什么二分能「不止查有序数组」
朴素二分解决的问题是：在整体有序数组里找一个值，每次和中间值比，砍掉不可能的一半。但「有序」只是单调性的一种特例——更本质的判断是：
是否存在一个量
x，使得某个判定check(x)的结果随x单调变化？
- 朴素二分：
x是下标，check(x)是nums[x] >= target。因为nums有序，check随下标单调（一旦true就一直true）。 - 旋转数组：下标空间上的「有序性」被旋转打破，但「哪半边有序」仍能判断，于是仍能折半。
- 二分答案：
x是候选答案，check(x)是「这个答案可不可行」。若答案越大越不可行，则check单调，可对答案值域二分。 - 三分：
x是自变量，f(x)单峰时，「极值在x左还是右」可以由两个内分点的函数值比较判定。
一旦把二分理解为「单调判定的折半搜索」，就会在很多意想不到的地方发现它能用——这是本叶所有变体的统一视角。
二、三变体速览对比
| 变体 | 对什么二分 | 单调性来源 | 典型复杂度 |
|---|---|---|---|
| 朴素二分 | 下标 | 数组整体有序 | O(log n) |
| 旋转数组搜索 | 下标 | 两段各自有序（部分有序） | O(log n)（无重复）/ O(n)（有重复） |
| 二分答案 | 答案值域 | 可行性关于答案单调 | O(log V × check) |
| 三分法 | 自变量 | 函数单峰/单谷（凸性） | O(log n)（底数 1.5） |
三、三种变体的共性
- 依赖广义单调性：无论形式如何，根本都是「有一侧可以安全排除」。
- 每轮排除常数比例：二分排除一半，三分排除三分之一——共同点是几何级数缩区间，所以都是对数级。
- 难点在判定（
check/ 分支条件），不在模板：朴素二分模板极简，难的是旋转数组的分支、二分答案的check设计、三分的极值方向判断。
四、与朴素二分的关键区别
- 朴素二分：判定
nums[mid]与target的大小关系，方向由「大小」直接决定。 - 旋转数组：判定变复杂——先判断
mid在哪段、哪半有序，再判断目标在不在那半，是两层判定。 - 二分答案：判定从「大小比较」换成「调用
check函数」，搜索对象从「下标」换成「值域」。 - 三分：判定从「一次比较」换成「两个内分点的函数值比较」，目标从「找定值」换成「找极值」。
下一步
理解了二分的广义化后，先看部分有序如何折半——旋转数组搜索是分支判定最繁的变体，见旋转数组搜索。