02.5.1.2 旋转数组与部分有序
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找
02.5.1.2-001 旋转排序数组是什么结构?
一句话结论
原升序数组在某断点旋转,拆成两段各自有序的非递减子数组,且前段元素整体大于后段;例如 [4,5,6,7,0,1,2];二分需先判断哪一半有序。
概念解释
- 两段有序。
- 断点两侧大小关系。
- 全局非单调。
原理流程
- 找断点。
- 分段有序。
- 判定目标落在哪段。
代码 / 图示
[4,5,6,7 | 0,1,2]
断点后段小于前段
常见误区
- 误区:旋转数组全局有序;正解:只分段有序。
- 误区:断点位置固定;正解:断点任意。
追问
- Q:无旋转算退化情形吗? A:算,断点在末尾。
- Q:降序旋转? A:比较方向相应反转。
02.5.1.2-002 搜索旋转排序数组(LC 33,无重复)怎么做?
一句话结论
每次中点先判断左半还是右半有序;目标落在有序区间内则收缩该侧,否则去另一侧;O(log n);数组无重复元素。
概念解释
- 分段有序判定。
- 目标区间归属。
- 折半排除。
原理流程
- 中点命中返回。
a[l] <= a[mid]左半有序。- 判定目标在左半有序区间则收缩左,否则右。
代码 / 示例
public int search(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) return mid;
if (a[l] <= a[mid]) { // 左半有序
if (a[l] <= target && target < a[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (a[mid] < target && target <= a[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
常见误区
- 误区:直接按全局有序比较;正解:先分哪半有序。
- 误区:有序区间判定漏等号;正解:
a[l]<=a[mid]含单边有序。
追问
- Q:为什么左半条件用
<=? A:l==mid时左半单点也有序。 - Q:找不到返回? A:-1。
02.5.1.2-003 含重复元素(LC 81)怎么处理?
一句话结论
当 a[l] == a[mid] 无法判断哪半有序,只能 l++ 收缩跳过重复;最坏退化 O(n),平均 O(log n);其余判定同无重复版本。
概念解释
- 等值模糊方向。
- 单点收缩。
- 最坏退化。
原理流程
- 命中返回。
- 等值无法分段则
l++。 - 其余按有序段判定。
代码 / 示例
public boolean search(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) return true;
if (a[l] == a[mid]) { l++; continue; }
if (a[l] < a[mid]) {
if (a[l] <= target && target < a[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (a[mid] < target && target <= a[r]) l = mid + 1;
else r = mid - 1;
}
}
return false;
}
常见误区
- 误区:有重复仍保证 O(log n);正解:最坏 O(n)。
- 误区:等值时直接猜方向;正解:无法判断只能收缩。
追问
- Q:最坏什么数据? A:大量首尾相等,断点无法定位。
- Q:去重后再二分? A:题目一般不允许预处理。
02.5.1.2-004 找旋转数组最小值(LC 153,无重复)怎么做?
一句话结论
最小值是断点后段首元素;中点大于右界则断点在右半,否则在左半;收缩到区间只剩一个即最小值;O(log n)。
概念解释
- 断点即最小值。
- 比较中点与右界。
- 收缩定位。
原理流程
a[mid] > a[r]:最小值在右。- 否则在左(含 mid)。
- 终止返回。
代码 / 示例
public int findMin(int[] a) {
int l = 0, r = a.length - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] > a[r]) l = mid + 1;
else r = mid;
}
return a[l];
}
常见误区
- 误区:与左界比较定位最小值;正解:与右界比较更稳,避免无旋转歧义。
- 误区:无旋转时仍找断点;正解:
r=mid自然收敛到首元素。
追问
- Q:为什么不用
a[l]比较? A:无旋转时a[l]最小,比较方向会矛盾。 - Q:最小值下标? A:返回 l。
02.5.1.2-005 含重复的最小值(LC 154)怎么做?
一句话结论
a[mid] > a[r] 收缩左界;a[mid] < a[r] 收缩右界;相等时 r-- 跳过重复;最坏 O(n);最小值不变性。
概念解释
- 等值无法定位。
- 右界收缩。
- 最坏退化。
原理流程
- 比较 mid 与 r。
- 大小分侧。
- 等值
r--。
代码 / 示例
public int findMin(int[] a) {
int l = 0, r = a.length - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] > a[r]) l = mid + 1;
else if (a[mid] < a[r]) r = mid;
else r--;
}
return a[l];
}
常见误区
- 误区:等值时
l++;正解:与右界比较口径下r--。 - 误区:重复数据仍 O(log n);正解:最坏 O(n)。
追问
- Q:最小值可能在被跳过的位置吗? A:等值时最小值两侧都可能,
r--不丢最小值。 - Q:与 LC 153 区别? A:多等值分支。
02.5.1.2-006 怎么判断哪一半有序?
一句话结论
无重复时 a[l] <= a[mid] 左半有序(l==mid 单点也算),否则右半有序;有序段满足端点大小关系;再用端点判定目标归属。
概念解释
- 端点比较。
- 单点有序。
- 分段归属。
原理流程
- 比较左界与中点。
- 左半有序或右半有序。
- 目标区间判定。
代码 / 图示
a[l] <= a[mid] → 左半有序
否则 → 右半有序
常见误区
- 误区:
a[l] < a[mid]漏掉单点;正解:用<=。 - 误区:两段同时判有序;正解:旋转数组至多一段在本轮有序。
追问
- Q:完全有序数组? A:左半恒有序,退化为普通二分。
- Q:等值时? A:无法判断,收缩跳过。
02.5.1.2-007 目标是否在有序区间怎么判定?
一句话结论
左半有序:a[l] <= target && target < a[mid] 进左半;右半有序:a[mid] < target && target <= a[r] 进右半;端点等号按区间开闭写清。
概念解释
- 区间端点。
- 闭区间判定。
- 排除另一侧。
原理流程
- 确定有序段。
- 端点夹逼 target。
- 命中区间收缩,否则反向。
代码 / 图示
左半:[a[l], a[mid])
右半:(a[mid], a[r]]
常见误区
- 误区:端点等号漏写导致边界值走错侧;正解:与区间口径一致。
- 误区:用无序段端点夹逼;正解:只在有序段内夹逼。
追问
- Q:target 等于 mid? A:开头已命中返回。
- Q:有序段为空? A:
l==mid单点,判定退化为等值比较。
02.5.1.2-008 旋转数组二分为什么仍能 O(log n)?
一句话结论
无重复时每轮至少有一段有序,可据端点排除一半;区间严格折半;含重复时等值轮次无法排除,最坏退化 O(n)。
概念解释
- 半段有序保证排除。
- 折半收敛。
- 重复退化。
原理流程
- 每轮判定有序段。
- 排除不含目标侧。
- 规模减半。
代码 / 图示
无重复:O(log n)
有重复:平均 O(log n),最坏 O(n)
常见误区
- 误区:旋转数组不能二分;正解:分段有序仍可折半。
- 误区:有重复也报 O(log n);正解:最坏 O(n)。
追问
- Q:O(log n) 前提? A:无重复或重复不影响分段判定。
- Q:n 很大重复多? A:退化线性,考虑预处理。
02.5.1.2-009 数组原地轮转是什么思路?
一句话结论
把数组后 k 位移到前部:三次反转(整体反转、前 k 反转、后 n-k 反转)原地完成;O(n) 时间 O(1) 空间;与二分找断点是两类问题。
概念解释
- 反转拼接。
- 原地交换。
- 非二分。
原理流程
- 整体反转。
- 前 k 反转。
- 后段反转。
代码 / 示例
void rotate(int[] a, int k) {
k %= a.length;
reverse(a, 0, a.length - 1);
reverse(a, 0, k - 1);
reverse(a, k, a.length - 1);
}
常见误区
- 误区:轮转问题用二分;正解:反转法 O(n)。
- 误区:k 未取模;正解:k 可能大于 n。
追问
- Q:额外数组做法? A:复制到新数组按位置回填 O(n) 空间。
- Q:LC 189? A:本框架对应。
02.5.1.2-010 怎么求旋转了多少次(断点下标)?
一句话结论
断点即最小值下标;找最小值位置 k,前 k 个元素被转到末尾;无旋转 k=0;复用最小值二分模板。
概念解释
- 断点 = 最小值位置。
- 旋转次数。
- 无旋转基准。
原理流程
- 二分定位最小值下标。
- 该下标即断点。
- 次数 = 下标。
代码 / 图示
[4,5,6,7,0,1,2] 最小值下标 4 → 旋转 4 位
常见误区
- 误区:断点是最大值位置;正解:旋转后最小值为首断点。
- 误区:无旋转断点记为 n;正解:k=0。
追问
- Q:多次旋转等价一次? A:取模合并。
- Q:重复元素断点唯一吗? A:最小值可能多处。
02.5.1.2-011 部分有序数组的通用二分思路是什么?
一句话结论
先识别有序区段(端点比较),在有序段内判定目标归属;无法保证全局单调时,靠分段单调性排除一侧;每轮必须能排除至少一半。
概念解释
- 分段单调。
- 区段判定。
- 排除一半。
原理流程
- 找有序段。
- 端点夹逼。
- 排除另一侧。
代码 / 图示
有序段 → 夹逼 → 收缩
常见误区
- 误区:部分有序直接全局比较;正解:先分段。
- 误区:无法排除一半仍硬二分;正解:退化线性。
追问
- Q:山峰数组? A:局部单调,比较两侧斜率。
- Q:二维部分有序? A:见 02.5.1.4。
02.5.1.2-012 旋转数组有哪些边界用例?
一句话结论
无旋转、单元素、两元素、全部相等、断点在首尾、target 等于端点、重复首尾;检查分段判定与等值退化。
概念解释
- 退化情形。
- 端点等值。
- 重复退化。
原理流程
- 无旋转走普通二分。
- 单点直接返回。
- 等值分支收缩。
代码 / 图示
[1,2,3] / [1] / [2,1]
全相等 / target=端点
常见误区
- 误区:无旋转仍判断点;正解:自然退化为普通二分。
- 误区:两元素分段误判;正解:
l==mid视为单点有序。
追问
- Q:空数组? A:返回 -1/false。
- Q:target 不存在? A:区间收敛后判 -1。
02.5.1.2-013 无旋转退化情形怎么处理?
一句话结论
数组完全有序时,左半恒有序,判定等价于普通二分;模板无需特判,a[l]<=a[mid] 恒成立;自然走普通收缩路径。
概念解释
- 恒有序段。
- 模板兼容。
- 无需特判。
原理流程
- 比较左界中点。
- 恒左半有序。
- 普通夹逼收缩。
代码 / 图示
[1,2,3,4,5]:左半恒有序
常见误区
- 误区:额外判断是否旋转;正解:模板兼容退化。
- 误区:无旋转走右半分支;正解:端点关系决定。
追问
- Q:降序退化? A:比较方向反转。
- Q:怎么自测退化? A:用有序数组跑模板。
02.5.1.2-014 重复元素为什么会退化线性?
一句话结论
a[l]==a[mid] 时左右段端点相等,无法判断断点在哪侧,只能逐点收缩;大量重复时每轮排除极少,最坏 O(n)。
概念解释
- 信息不足。
- 单点收缩。
- 退化线性。
原理流程
- 等值无法分段。
l++或r--。- 区间仅减一。
代码 / 图示
[1,1,1,1,2,1,1] 等值轮次无法折半
常见误区
- 误区:重复元素仍 O(log n);正解:最坏 O(n)。
- 误区:等值时猜一侧;正解:可能漏解。
追问
- Q:LC 81 最坏复杂度? A:O(n)。
- Q:怎么优化重复场景? A:预处理去重(题意允许时)。
02.5.1.2-015 旋转数组二分常见错误有哪些?
一句话结论
边方向写反、有序段判定漏等号、有序段外用无序端点夹逼、等值未收缩、端点等号错位、无旋转误判断点;按分段判定 → 夹逼 → 收缩复核。
概念解释
- 方向。
- 判定条件。
- 夹逼口径。
原理流程
- 复核哪半有序。
- 复核夹逼端点。
- 复核等值分支。
代码 / 图示
有序段判定 → 区间夹逼 → 边界更新
常见误区
- 误区:把
a[mid]当有序端点;正解:用段两端点。 - 误区:target 等于端点走错侧;正解:等号归属写清。
追问
- Q:怎么自测? A:构造断点在不同位置的样例。
- Q:找不到元素? A:检查端点夹逼是否过严。
02.5.1.2-016 二分找断点与普通最小值查找有何区别?
一句话结论
普通有序数组最小值在端点;旋转数组最小值为断点,需比较中点与右界定位;本质都是二分单调性质,只是比较参照点不同。
概念解释
- 有序:端点已知。
- 旋转:断点未知。
- 比较参照。
原理流程
- 有序取端点。
- 旋转比较 mid 与 r。
- 收缩到断点。
代码 / 图示
有序:a[0] 最小
旋转:mid > a[r] → 右半找
常见误区
- 误区:旋转最小值仍取左端点;正解:左端点是前段最大附近。
- 误区:比较参照混用;正解:固定与右界比。
追问
- Q:峰值数组找最大值? A:对称比较。
- Q:断点与最小值关系? A:旋转后同一位置。
02.5.1.2-017 旋转数组与二分查找基础题怎么衔接?
一句话结论
先掌握 02.5.1.1 区间不变量与上下界模板,再在分段有序场景中加“哪半有序”判定;收缩方向仍由区间口径保证;新增分支不改变二分框架。
概念解释
- 框架复用。
- 分段判定附加。
- 口径不变。
原理流程
- 固定区间口径。
- 加有序段判定。
- 套用夹逼收缩。
代码 / 图示
基础二分 + 分段判定 = 旋转二分
常见误区
- 误区:旋转题另起一套死循环口径;正解:复用基础模板。
- 误区:新增分支破坏不变量;正解:候选侧仍保留。
追问
- Q:学旋转题前先掌握什么? A:lower_bound 与边界更新。
- Q:分段判定属于哪一步? A:比较后的排除侧选择。
02.5.1.2-018 旋转数组复杂度怎么汇报?
一句话结论
无重复 O(log n) 时间 O(1) 空间;含重复平均 O(log n)、最坏 O(n);找最小值同口径;空间均 O(1) 迭代。
概念解释
- 折半对数。
- 重复退化。
- 辅助常数。
原理流程
- 标注是否有重复。
- 每轮排除规模。
- 分列时间空间。
代码 / 图示
无重复:O(log n) / O(1)
有重复:最坏 O(n) / O(1)
常见误区
- 误区:旋转数组统一 O(log n);正解:重复最坏 O(n)。
- 误区:递归实现不计栈;正解:迭代 O(1)。
追问
- Q:找最小值与查找 target 同复杂度吗? A:同口径。
- Q:n 规模下 O(n) 可接受吗? A:重复多需考虑其他方案。
02.5.1.2-019 旋转数组题有哪些常见追问?
一句话结论
有重复怎么办、断点在哪、无旋转是否兼容、为什么与右界比较、最坏复杂度、能否求旋转次数;都围绕分段判定与等值退化回答。
概念解释
- 重复处理。
- 断点定位。
- 复杂度口径。
原理流程
- 说明分段判定。
- 说明等值退化。
- 报复杂度。
代码 / 图示
重复 → 收缩退化
断点 → 最小值位置
常见误区
- 误区:追问重复时仍答 O(log n);正解:说明最坏 O(n)。
- 误区:说不清比较参照;正解:固定 mid 与 r。
追问
- Q:两数相乘旋转? A:与二分无关。
- Q:环形有序数组? A:同旋转模型。
02.5.1.2-020 部分有序二分常见变体有哪些?
一句话结论
旋转查找、找最小值、旋转次数、山峰数组、局部峰谷、两段拼接有序数组;主线是识别有序段 + 端点夹逼 + 保留候选侧。
概念解释
- 框架:分段二分。
- 变体:峰谷/拼接。
- 场景包装。
原理流程
- 识别单调段。
- 判定归属。
- 收缩区间。
代码 / 图示
分段有序 → 夹逼 → 折半
常见误区
- 误区:变体题脱离二分框架;正解:先找可排除一半的性质。
- 误区:无序段端点参与夹逼;正解:只在有序段内判定。
追问
- Q:山峰数组峰值(LC 162)? A:比较中点与右侧,高处侧收缩。
- Q:拼接有序数组合并? A:归并思路见 02.5.2.3。