【面试高频题】二分法：搜索旋转排序数组（含重复元素，返回最小索引）

文章目录

• 前言
• 一、什么是旋转数组？
• • 1. 核心定义
  • 2. 旋转数组的形态
• 二、问题完整描述
• 三、解题思路分析
• • 方案1：先找旋转点（pivot），再二分查找
  • • 1. 方案步骤
    • 2. 关键子问题实现
    • • 查找真正旋转点pivot（处理重复元素）
      • 区间内找第一个匹配元素的二分查找
  • 方案2：优化二分查找法
  • • 1. 核心思路
    • 2. 关键逻辑
• 总结

前言

在算法面试中，“搜索旋转排序数组（LeetCode 面试题 10.03）” 是经典的二分查找变种题，既考察对旋转数组特性的理解，也考验二分查找的灵活运用。本文会从基础概念到解题思路，再到代码实现，全方位拆解这道题。

一、什么是旋转数组？

1. 核心定义

旋转数组（Rotated Sorted Array）是指原本严格升序排列的数组，经过若干次 “旋转操作” 后得到的数组。 旋转操作的定义：将数组的最后一个元素移动到数组开头，完成一次旋转。多次旋转就是重复该操作。

2. 旋转数组的形态

以升序数组 [0, 1, 2, 4, 5, 6, 7] 为例：

• 旋转 1 次后：[7, 0, 1, 2, 4, 5, 6]（最后一个元素 7 移到开头）
• 旋转 2 次后：[6, 7, 0, 1, 2, 4, 5]（最后一个元素 6 移到开头）
• 旋转 3 次后：[5, 6, 7, 0, 1, 2, 4]（最后一个元素 5 移到开头）

旋转数组的特点：虽然整体不再有序，但数组被分成两个有序的部分。例如，在旋转2次后的数组 [6, 7, 0, 1, 2, 4, 5] 中：

• 第一部分 [6, 7] 是有序的
• 第二部分 [0, 1, 2, 4, 5] 也是有序的
• 中间的断点（叫做 pivot / 旋转点）断点的位置是数组的最小值，但最小值并不一定只在断点位置。比如：[1, 1, 1, 1, 1, 2, 1, 1, 1]，该数组的断点位置在索引 6 上，最小值为1，还有其他位置值也是 1。

二、问题完整描述

给定一个包含n个整数的旋转排序数组（原数组为升序排列，旋转次数未知）。请编写代码找出数组中目标元素的最小索引：

• 若目标元素存在，返回索引值最小的那个（多个相同元素时）；
• 若目标元素不存在，返回 -1。

实例解释：

• 实例1：无重复元素
  • 输入：nums = [3, 4, 5, 1, 2] , target = 1
  • 输出：3
  • 解释：数组是原升序数组 [1,2,3,4,5] 旋转 3 次的结果，1 出现在索引 3 的位置，且是唯一位置。
• 实例 2：含重复元素（需返回最小索引）
  • 输入：nums = [2, 2, 2, 0, 1, 2]，target = 2
  • 输出：0
  • 解释：2 出现在索引 0、1、2、5，需返回最小的索引 0。
• 实例 3：目标元素不存在
  • 输入：nums = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
  • 输出：11 没有在数组中，返回 -1；

三、解题思路分析

针对这道题，有两种主流解法：暴力遍历（简单但低效）、优化二分查找（高效但需处理边界）。 暴力遍历简单，时间复杂度高，这里不做讨论。

方案1：先找旋转点（pivot），再二分查找

1. 方案步骤

• 找旋转点：通过二分查找找到数组的旋转点 pivot，将数组划分为两个升序子数组：
  • 左区间：[0, pivot-1]（若 pivot>0，则该区间升序）；
  • 右区间：[pivot, n-1]（必然升序）。
• 分区间二分查找：
  • 先在左区间 [0, pivot-1] 中二分查找目标元素，若找到则返回该区间内第一个匹配的索引（保证最小）；
  • 若左区间未找到，再在右区间 [pivot, n-1] 中二分查找，返回第一个匹配的索引；
  • 若两个区间都未找到，返回 -1。

2. 关键子问题实现

查找真正旋转点pivot（处理重复元素）

旋转点的查找是该方案的核心前置步骤，该步骤需要分为两步：

• Step A：二分找到任意一个最小值的索引 p 这是经典的 “旋转数组找最小值（LeetCode 153）” 的二分逻辑，核心是通过对比 nums[mid] 和 nums[right] 缩小范围：
  • 初始化 left = 0，right = nums.size() – 1，循环条件 left < right：
  • 计算 mid = left + (right – left) / 2（避免整数溢出）；
  • 分情况讨论：
    • 情况 1：nums[mid] > nums[right] → 最小值在 mid 右侧（右半段无序），left = mid + 1；
    • 情况 2：nums[mid] < nums[right] → 最小值在 mid 左侧（包括 mid），right = mid；
    • 情况 3：nums[mid] == nums[right] → 重复元素无法判断最小值的位置，right–（缩小范围，不影响最小值查找）；
  • 循环结束时，left == right，得到任意一个最小值的索引 p。
• Step B：从 p 向左修正为最小值块的起点（真正断点pivot）
  • 关键观察：在环形视角下，所有最小值会连成一个连续块；真正断点就是这个最小值块的“起点”（它前面一定是更大的数）。
  • 所以我们从 p 开始，沿着**左边（循环）**一直走，走到最小值块的最左端，那个位置就是断点pivot。

测试用例验证

• 测试用例 1：[5,5,5,1,2,3,4,5]（真正断点是 3）

Step A：
l=0, r=7 → mid=3（nums[3]=1 < nums[7]=5）→ r=3；
l=0<3 → mid=1（nums[1]=5 > nums[3]=1）→ l=2；
l=2<3 → mid=2（nums[2]=5 > nums[3]=1）→ l=3；
循环结束，p=3，minVal=1。

Step B：
start=3 → prev=(3-1+8)%8=2（nums[2]=5≠minVal）→ break；
返回p=3（正确）。

• 测试用例 2：[2,1,2,2,2]（真正断点是 1）

Step A：
l=0, r=4 → mid=2（nums[2]=2 == nums[4]=2）→ r=3；
l=0<3 → mid=1（nums[1]=1 < nums[3]=2）→ r=1；
l=0<1 → mid=0（nums[0]=2 > nums[1]=1）→ l=1；
循环结束，p=1，minVal=1。

Step B：
start=1 → prev=(1-1+5)%5=0（nums[0]=2≠minVal）→ break；
返回p=1（正确）。

• 测试用例 3：[1,1,1,1,1,2,1,1,1]（真正断点是 6）

Step A：
l=0, r=8 → mid=4（nums[4]=1 == nums[r]=1）→ r=7；
l=0<7 → mid=3（nums[1]=1 == nums[7]=1）→ r=6；
l=0<6 → mid=3（nums[3]=1 == nums[6]=1）→ r=5；
l=0<5 → mid=2（nums[2]=1 < nums[5]=2）→ r=2；
l=0<2 → mid=1（nums[1]=1 == nums[2]=1）→ r=1；
l=0<1 → mid=0（nums[0]=1 == nums[1]=1）→ r=0；
循环结束，p=0，minVal=1。

Step B：
start=0 → prev=(0-1+9)%9=8≠start（nums[8]=1 == minVal → p更新为8）；
prev=(8-1+9)%9=7≠start（nums[7]=1 == minVal → p更新为7）；
prev=(7-1+9)%9=6≠start（nums[6]=1 == minVal → p更新为6）；
prev=(6-1+9)%9=5≠start（nums[5]=2 ≠ minVal → 触发break，退出循环）；
返回p=6（正确）。

• 测试用例 4：[3,4,5,1,2]（真正断点是 3）

Step A：
l=0, r=4 → mid=2（nums[2]=5 > nums[4]=1）→ l=3；
l=3<4 → mid=3（nums[3]=1 < nums[4]=2）→ r=3；
循环结束，p=3，minVal=1。

Step B：
start=3 → prev=(3-1+5)%5=2（nums[2]=5≠minVal）→ break；
返回p=3（正确）。

C++ 代码实现

// 子函数1：查找旋转数组的真正旋转点
int findPivot(vector<int>& nums) {
int n = (int)nums.size();
if (n == 0) return –1; // 也可按题意返回 0

// ——– Step A：二分找最小值的某个索引 p（允许重复）——–
int l = 0, r = n – 1;
while (l < r) {
int mid = l + (r – l) / 2;
if (nums[mid] > nums[r]) {
l = mid + 1;
}else if (nums[mid] < nums[r]) {
r = mid;
} else {
// nums[mid] == nums[r]，信息不足，缩右边界（最坏会退化到 O(n)）
r—;
}
}
int p = l; // 某个最小值位置
int minVal = nums[p];

// ——– Step B：把 p 修正为“真正断点”（最小值块的起点）——–
int start = p;
while (true) {
int prev = (p – 1 + n) % n;
if (prev == start) {
// 全数组都等于 minVal（全相等），没有“真正下降”，按定义返回 0
return 0;
}
if (nums[prev] == minVal) {
p = prev; // 还在最小值块里，继续向左（环形）扩
} else {
break; // p 已是最小值块起点：它前面不是 minVal（若旋转，通常更大）
}
}

// p 就是“第一次下降”的位置（真正旋转断点）
// 你也可以加一行断言：p==0 || nums[p] < nums[p-1]
return p;
}

区间内找第一个匹配元素的二分查找

普通二分查找可能返回任意匹配索引，需改造为找区间内第一个出现的目标元素：

• 初始化 start（区间左边界）、end（区间右边界）；
• 循环条件 start < end：
  • 计算 mid = start + (end – start) / 2；
  • 若 nums[mid] >= target → 目标在左半段（收缩右边界），end = mid；
  • 否则 → 目标在右半段，start = mid + 1；

C++ 代码实现

// 子函数2：在[start, end]区间内二分查找target的第一个出现索引，未找到返回-1
int binarySearchFirst(vector<int>& nums, int start, int end, int target) {
while (start < end) {
int mid = start + (end – start) / 2;
if (nums[mid] >= target) {
// 目标在左半段，收缩右边界（找第一个匹配项）
end = mid;
} else {
// 目标在右半段
start = mid + 1;
}
}
// 验证最终收敛的元素是否为目标
return (start <= end && nums[start] == target) ? start : –1;
}

// 主函数：先找旋转点，再分区间二分查找
int searchRotatedArray(vector<int>& nums, int target) {
if (nums.empty()) return –1; // 空数组直接返回-1

// 步骤1：找到真正旋转点
int pivot = findPivot(nums);
int n = nums.size();

// 步骤2：先查左区间[0, pivot-1]（升序）
int leftResult = binarySearchFirst(nums, 0, pivot – 1, target);
if (leftResult != –1) {
return leftResult; // 左区间找到，直接返回（保证最小索引）
}

// 步骤3：左区间未找到，查右区间[pivot, n-1]（升序）
int rightResult = binarySearchFirst(nums, pivot, n – 1, target);
return rightResult;
}

复杂度分析：

• 平均：O(log n)（pivot 二分 + 两次 lower_bound）
• 最坏：O(n)（当大量重复导致真正的 pivot 查找时频繁 right–）
• 空间：O(1)

方案2：优化二分查找法

1. 核心思路

旋转数组的核心特性是 “局部有序”（数组的左半段或右半段必然升序），基于这一特性通过二分查找缩小搜索范围；核心目标是找到目标值的最小索引，因此优先验证左边界（索引天然更小），同时处理 “重复元素导致无法判断区间有序性” 的场景，通过 “记录候选索引 + 向左收缩” 保证最终找到最小索引（无则返回 – 1）。

2. 关键逻辑

• 初始化与边界处理
  • 若数组为空（n=0），直接返回 – 1（无元素可查）；
  • 初始化左右指针：left=0（左边界）、right=n-1（右边界）；
  • 初始化ans=-1（记录找到的目标值候选索引，未找到则保持 – 1）。
• 循环搜索（left ≤ right） 循环条件覆盖所有可能的搜索范围，保证不遗漏任何索引。
  • Step 0：最小索引保底（最高优先级） 每次循环优先检查左边界nums[left]：若等于target，直接返回left（左边界索引是当前最小，无需继续搜索）。
  • Step 1：中间索引计算 mid = left + (right – left) / 2：避免left+right导致的整数溢出，等价于(left+right)/2。
  • 命中目标值的处理
    • 若nums[mid] == target：
    • 先记录ans=mid（保存当前命中的索引，作为候选）；
    • 收缩右边界right=mid-1（继续向左搜索更小的索引）；
    • continue跳过后续判断，进入下一轮循环。
  • Step 2：处理“重复导致无法判定有序半边”的情况 若nums[left] == nums[mid] && nums[mid] == nums[right]（三段值全相同，无法判断哪段有序）：
    • 同时收缩 left++、right–（快速缩小搜索范围）；
    • continue 跳过后续判断，进入下一轮循环。
    • 为什么 left++ 是安全的？
      • 因为我们在 Step 0 已经检查过 nums[left] != target
      • 所以把这个 left 丢掉不会丢答案（更不会丢“最小索引答案”）
    • 为什么 right– 也安全？
      • 我们找的是最小索引，砍掉右侧只会让区间更小，不会丢掉更小的答案
      • 同时也能保证循环推进，避免卡死
  • Step 3：区间有序性判断与范围收缩 基于 “局部有序” 特性，判断左 / 右半段是否有序，并收缩范围：
    • 若 nums[left] <= nums[mid]：左半段有序
      • 如果 target 落在左半段的值域：nums[left] <= target < nums[mid]
        • 说明答案一定在左边：right = mid – 1
      • 否则去右边：left = mid + 1
    • 否则：右半段有序
      • 如果 target 落在右半段值域：nums[mid] < target <= nums[right]
        • 去右边：left = mid + 1
      • 否则去左边：right = mid – 1

int searchRotatedArray(vector<int>& nums, int target) {
int n = (int)nums.size();
if (n == 0)
return –1;

int left = 0, right = n – 1;
int ans = –1; // 记录找到的目标索引（候选）

while (left <= right) {
// 核心兜底：左边界是目标值，直接返回（最小索引）
if (nums[left] == target)
return left;

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

// 情况1：找到目标，记录候选+向左收缩找更小索引
if (nums[mid] == target) {
ans = mid; // 保存当前命中位置
right = mid – 1; // 继续往左找更小索引
continue; // 跳过后续判断，进入下一轮循环
}

// 情况2：全段重复（无法判断有序），同时收缩左右边界
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right—;
continue; // 跳过后续判断，进入下一轮循环
}

// 情况3：左半段有序（包含nums[left]==nums[mid]的非全段重复场景）
if (nums[left] <= nums[mid]) {
// 目标在左半段 → 收缩右边界
if (nums[left] <= target && target < nums[mid])
right = mid – 1;
// 目标在右半段 → 收缩左边界
else
left = mid + 1;
}
// 情况4：右半段有序
else {
// 目标在右半段 → 收缩左边界
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
// 目标在左半段 → 收缩右边界
else
right = mid – 1;
}
}

// 循环结束，返回找到的最小索引（未找到则为-1）
return ans;
}

复杂度分析：

• 平均：接近 O(log n)（像普通二分）
• 最坏：O(n)（当大量重复导致频繁触发 nums[l]==nums[mid]==nums[r] 只能缩边界）
• 空间：O(1)

总结

核心要点回顾

旋转数组的查找问题，核心是对二分查找的灵活改造 —— 将 “无序数组” 转化为 “有序子数组” 的二分，同时兼顾业务要求（返回最小索引）。掌握这一思路，不仅能解决该问题，还能迁移到其他 “局部有序” 的数组查找场景中。