旋转排序数组中的目标查找：LeetCode 33 题的四种解法与二分搜索深度解析

旋转排序数组中的目标查找：LeetCode 33 题的四种解法与二分搜索深度解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文基于 leetcode 仓库中的 find-target-in-rotated-sorted-array.md 文档整理成文，系统讲解「搜索旋转排序数组」这道经典二分查找题：从 O(n) 的暴力扫描，到「先找旋转点再二分」的两趟法，再到一次遍历完成判断的单趟法，并逐一分析实现中的常见陷阱。读完本文，你将掌握如何利用旋转数组「两段有序子数组」的结构特性，把查找复杂度从线性降到 O(log n)，并能在多种编程语言之间迁移这套思路。

前置知识

在动手解这道题之前，建议先熟悉以下基础概念：

• 二分查找：每次将搜索区间减半的分治查找算法，是本题所有最优解的核心。仓库中的 binary-search.md 对标准二分查找有系统讲解，建议先阅读。
• 数组：理解数组索引机制，以及旋转操作如何改变有序数组的元素排布。
• 有序数组的性质：认识旋转后的有序数组可以看作「两个拼接在一起的有序子数组」。

题目背景：本题对应 LeetCode 第 33 题（Search in Rotated Sorted Array）。输入是一个按升序排列、且在某个未知位置旋转过的整数数组（例如[4,5,6,7,0,1,2]），要求查找目标值target的索引，不存在则返回-1。数组中的元素互不相同，且要求算法的时间复杂度为 O(log n)。仓库中该题的参考实现见 hints/find-target-in-rotated-sorted-array.md，其推荐目标是O(log n) 时间、O(1) 空间。

1. 暴力解法（Brute Force）

直觉

最简单直接的方式就是逐个检查数组中的每个元素。找到目标值就返回其索引；遍历完整个数组仍未找到，说明目标不存在，返回-1。该方法永远正确，但大数组下效率不高，忽略了旋转数组本身具备的有序结构。

算法流程

1. 从左到右遍历整个数组。
2. 对每个索引位置，将该元素与目标值比较。
3. 相等则返回该索引。
4. 循环结束仍未匹配，返回-1。

多语言实现

class Solution: def search(self, nums: List[int], target: int) -> int: for i in range(len(nums)): if nums[i] == target: return i return -1

class Solution { public int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { return i; } } return -1; } }

class Solution { public: int search(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); i++) { if (nums[i] == target) { return i; } } return -1; } };

class Solution { /** * @param {number[]} nums * @param {number} target * @return {number} */ search(nums, target) { for (let i = 0; i < nums.length; i++) { if (nums[i] == target) { return i; } } return -1; } }

public class Solution { public int Search(int[] nums, int target) { for (int i = 0; i < nums.Length; i++) { if (nums[i] == target) { return i; } } return -1; } }

func search(nums []int, target int) int { for i := 0; i < len(nums); i++ { if nums[i] == target { return i } } return -1 }

class Solution { fun search(nums: IntArray, target: Int): Int { for (i in nums.indices) { if (nums[i] == target) { return i } } return -1 } }

class Solution { func search(_ nums: [Int], _ target: Int) -> Int { for i in 0..<nums.count { if nums[i] == target { return i } } return -1 } }

impl Solution { pub fn search(nums: Vec<i32>, target: i32) -> i32 { for i in 0..nums.len() { if nums[i] == target { return i as i32; } } -1 } }

复杂度分析

• 时间复杂度：O(n)，最坏情况下要扫描整个数组。
• 空间复杂度：O(1)，只使用了常量级的额外空间。

2. 二分查找：先找旋转点（Pivot）

直觉

旋转后的有序数组本质上是两个有序子数组拼接在一起。核心思路分两步：

1. 找到旋转点（pivot）——即最小元素的索引，它标记了数组是在哪里发生旋转的。
2. 找到 pivot 之后，数组被切分为：
   • 左边一段有序子数组；
   • 右边一段有序子数组。
3. 判断目标可能落在哪一段，然后在该段上执行标准二分查找。

两次二分合起来，就能在对数时间内完成查找。这也与 hints/find-target-in-rotated-sorted-array.md 中 Hint 2 的思路一致：例如[3, 4, 1, 2]是旋转两次的结果，可以切分为两个有序段[3, 4]和[1, 2]，只要找到这个「拐点」（cut），就可以分别在两段上二分。

算法流程

1. 用二分查找定位pivot：
   • 比较中间元素与最右元素。
   • 若nums[mid] > nums[right]，说明 pivot 在右半段。
   • 否则，pivot 在左半段（含mid位置）。
2. 确定 pivot 后：
   • pivot 之前的子数组是一个有序段；
   • 从 pivot 开始的子数组是另一个有序段。
3. 先在左半段执行标准二分查找，找到则返回索引。
4. 否则在右半段执行标准二分查找。
5. 两段都找不到，返回-1。

多语言实现

class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] > nums[r]: l = m + 1 else: r = m pivot = l def binary_search(left: int, right: int) -> int: while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 result = binary_search(0, pivot - 1) if result != -1: return result return binary_search(pivot, len(nums) - 1)

public class Solution { public int search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int pivot = l; int result = binarySearch(nums, target, 0, pivot - 1); if (result != -1) { return result; } return binarySearch(nums, target, pivot, nums.length - 1); } public int binarySearch(int[] nums, int target, int left, int right) { while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } }

class Solution { public: int search(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int pivot = l; int result = binarySearch(nums, target, 0, pivot - 1); if (result != -1) { return result; } return binarySearch(nums, target, pivot, nums.size() - 1); } int binarySearch(vector<int>& nums, int target, int left, int right) { while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } };

class Solution { /** * @param {number[]} nums * @param {number} target * @return {number} */ search(nums, target) { let l = 0; let r = nums.length - 1; while (l < r) { const m = Math.floor((l + r) / 2); if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } const pivot = l; const result = this.binarySearch(nums, target, 0, pivot - 1); if (result !== -1) { return result; } return this.binarySearch(nums, target, pivot, nums.length - 1); } /** * @param {number[]} nums * @param {number} target * @param {number} left * @param {number} right * @return {number} */ binarySearch(nums, target, left, right) { while (left <= right) { const mid = Math.floor((left + right) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } }

public class Solution { public int Search(int[] nums, int target) { int l = 0, r = nums.Length - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int pivot = l; int result = BinarySearch(nums, target, 0, pivot - 1); if (result != -1) { return result; } return BinarySearch(nums, target, pivot, nums.Length - 1); } public int BinarySearch(int[] nums, int target, int left, int right) { while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } }

func search(nums []int, target int) int { l, r := 0, len(nums)-1 for l < r { m := (l + r) / 2 if nums[m] > nums[r] { l = m + 1 } else { r = m } } pivot := l var binarySearch func(left, right int) int binarySearch = func(left, right int) int { for left <= right { mid := (left + right) / 2 if nums[mid] == target { return mid } else if nums[mid] < target { left = mid + 1 } else { right = mid - 1 } } return -1 } result := binarySearch(0, pivot-1) if result != -1 { return result } return binarySearch(pivot, len(nums)-1) }

class Solution { fun search(nums: IntArray, target: Int): Int { var l = 0 var r = nums.size - 1 while (l < r) { val m = (l + r) / 2 if (nums[m] > nums[r]) { l = m + 1 } else { r = m } } val pivot = l fun binarySearch(left: Int, right: Int): Int { var left = left var right = right while (left <= right) { val mid = (left + right) / 2 when { nums[mid] == target -> return mid nums[mid] < target -> left = mid + 1 else -> right = mid - 1 } } return -1 } var result = binarySearch(0, pivot - 1) if (result != -1) { return result } return binarySearch(pivot, nums.size - 1) } }

class Solution { func search(_ nums: [Int], _ target: Int) -> Int { var l = 0, r = nums.count - 1 while l < r { let m = (l + r) / 2 if nums[m] > nums[r] { l = m + 1 } else { r = m } } let pivot = l func binarySearch(_ left: Int, _ right: Int) -> Int { var l = left, r = right while l <= r { let mid = (l + r) / 2 if nums[mid] == target { return mid } else if nums[mid] < target { l = mid + 1 } else { r = mid - 1 } } return -1 } let result = binarySearch(0, pivot - 1) if result != -1 { return result } return binarySearch(pivot, nums.count - 1) } }

impl Solution { pub fn search(nums: Vec<i32>, target: i32) -> i32 { let (mut l, mut r) = (0i32, nums.len() as i32 - 1); while l < r { let m = (l + r) / 2; if nums[m as usize] > nums[r as usize] { l = m + 1; } else { r = m; } } let pivot = l; let result = Self::binary_search(&nums, target, 0, pivot - 1); if result != -1 { return result; } Self::binary_search(&nums, target, pivot, nums.len() as i32 - 1) } fn binary_search(nums: &[i32], target: i32, mut left: i32, mut right: i32) -> i32 { while left <= right { let mid = (left + right) / 2; if nums[mid as usize] == target { return mid; } else if nums[mid as usize] < target { left = mid + 1; } else { right = mid - 1; } } -1 } }

复杂度分析

• 时间复杂度：O(log n)。找 pivot 一次二分，段内查找又一次二分，总复杂度仍为对数级。
• 空间复杂度：O(1)（若使用递归实现二分，则栈深度为 O(log n)）。

3. 二分查找：两趟法（Two Pass）

直觉

旋转后的数组就是「两个有序数组粘在一起」，因此可以把问题拆成两次简单的二分查找：

1. 第一次二分：找到 pivot——最小元素的索引，即旋转发生的位置。
2. 第二次二分：判断目标落在哪个有序段，然后只在该段上执行标准二分。

与上一节方案相比，区别在于不两段都搜：先通过 pivot 处的值与数组首尾值的关系，一次性确定目标所在的段，只搜一段。

算法流程

1. 二分定位pivot：
   • 比较中间元素与右端元素。
   • 若nums[mid] > nums[right]，pivot 在右侧。
   • 否则，pivot 在左侧（含mid位置）。
2. 找到 pivot 后：
   • 若target落在[nums[pivot], nums[最后]]区间内，搜索右半段；
   • 否则搜索左半段。
3. 在选定的半段上执行标准二分查找。
4. 找到返回索引，否则返回-1。

多语言实现

class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] > nums[r]: l = m + 1 else: r = m pivot = l l, r = 0, len(nums) - 1 if target >= nums[pivot] and target <= nums[r]: l = pivot else: r = pivot - 1 while l <= r: m = (l + r) // 2 if nums[m] == target: return m elif nums[m] < target: l = m + 1 else: r = m - 1 return -1

public class Solution { public int search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int pivot = l; l = 0; r = nums.length - 1; if (target >= nums[pivot] && target <= nums[r]) { l = pivot; } else { r = pivot - 1; } while (l <= r) { int m = (l + r) / 2; if (nums[m] == target) { return m; } else if (nums[m] < target) { l = m + 1; } else { r = m - 1; } } return -1; } }

class Solution { public: int search(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int pivot = l; l = 0; r = nums.size() - 1; if (target >= nums[pivot] && target <= nums[r]) { l = pivot; } else { r = pivot - 1; } while (l <= r) { int m = (l + r) / 2; if (nums[m] == target) { return m; } else if (nums[m] < target) { l = m + 1; } else { r = m - 1; } } return -1; } };

class Solution { /** * @param {number[]} nums * @param {number} target * @return {number} */ search(nums, target) { let l = 0, r = nums.length - 1; while (l < r) { let m = Math.floor((l + r) / 2); if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } let pivot = l; l = 0; r = nums.length - 1; if (target >= nums[pivot] && target <= nums[r]) { l = pivot; } else { r = pivot - 1; } while (l <= r) { let m = Math.floor((l + r) / 2); if (nums[m] === target) { return m; } else if (nums[m] < target) { l = m + 1; } else { r = m - 1; } } return -1; } }

public class Solution { public int Search(int[] nums, int target) { int l = 0, r = nums.Length - 1; while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) { l = m + 1; } else { r = m; } } int pivot = l; l = 0; r = nums.Length - 1; if (target >= nums[pivot] && target <= nums[r]) { l = pivot; } else { r = pivot - 1; } while (l <= r) { int m = (l + r) / 2; if (nums[m] == target) { return m; } else if (nums[m] < target) { l = m + 1; } else { r = m - 1; } } return -1; } }

func search(nums []int, target int) int { l, r := 0, len(nums)-1 for l < r { m := (l + r) / 2 if nums[m] > nums[r] { l = m + 1 } else { r = m } } pivot := l l, r = 0, len(nums)-1 if target >= nums[pivot] && target <= nums[r] { l = pivot } else { r = pivot - 1 } for l <= r { m := (l + r) / 2 if nums[m] == target { return m } else if nums[m] < target { l = m + 1 } else { r = m - 1 } } return -1 }

class Solution { fun search(nums: IntArray, target: Int): Int { var l = 0 var r = nums.size - 1 while (l < r) { val m = (l + r) / 2 if (nums[m] > nums[r]) { l = m + 1 } else { r = m } } val pivot = l l = 0 r = nums.size - 1 if (target >= nums[pivot] && target <= nums[r]) { l = pivot } else { r = pivot - 1 } while (l <= r) { val m = (l + r) / 2 if (nums[m] == target) { return m } else if (nums[m] < target) { l = m + 1 } else { r = m - 1 } } return -1 } }

class Solution { func search(_ nums: [Int], _ target: Int) -> Int { var l = 0, r = nums.count - 1 while l < r { let m = (l + r) / 2 if nums[m] > nums[r] { l = m + 1 } else { r = m } } let pivot = l l = 0 r = nums.count - 1 if target >= nums[pivot] && target <= nums[r] { l = pivot } else { r = pivot - 1 } while l <= r { let m = (l + r) / 2 if nums[m] == target { return m } else if nums[m] < target { l = m + 1 } else { r = m - 1 } } return -1 } }

impl Solution { pub fn search(nums: Vec<i32>, target: i32) -> i32 { let (mut l, mut r) = (0i32, nums.len() as i32 - 1); while l < r { let m = (l + r) / 2; if nums[m as usize] > nums[r as usize] { l = m + 1; } else { r = m; } } let pivot = l; l = 0; r = nums.len() as i32 - 1; if target >= nums[pivot as usize] && target <= nums[r as usize] { l = pivot; } else { r = pivot - 1; } while l <= r { let m = (l + r) / 2; if nums[m as usize] == target { return m; } else if nums[m as usize] < target { l = m + 1; } else { r = m - 1; } } -1 } }

复杂度分析

• 时间复杂度：O(log n)。找 pivot 一次二分 + 段内一次二分。
• 空间复杂度：O(1)。

4. 二分查找：单趟法（One Pass）

直觉

前两种方案都需要先单独找到 pivot，再做第二次二分。单趟法把两步合并成一次遍历：每次迭代中，利用「左半段有序」或「右半段有序」这一性质，直接决定目标落在哪一侧，从而收缩区间。

其正确性依据来自提示中 Hint 3 与 Hint 4 的观察：指针l、mid、r三者中，至少有两个落在同一个有序段内。于是：

• 若nums[l] <= nums[mid]，说明左半段[l, mid]整体有序（pivot 不在其中），可以据此判断 target 是否落在该区间内；
• 否则说明右半段[mid, r]整体有序，依据 target 与区间端点的关系决定收缩方向。

算法流程

1. 初始化l = 0, r = len(nums) - 1。
2. 循环条件l <= r：
   • 计算mid，若nums[mid] == target直接返回mid。
   • 若nums[l] <= nums[mid]（左段有序）：
     • 若target > nums[mid]或target < nums[l]，说明 target 不在左段，l = mid + 1；
     • 否则r = mid - 1。
   • 否则（右段有序）：
     • 若target < nums[mid]或target > nums[r]，说明 target 不在右段，r = mid - 1；
     • 否则l = mid + 1。
3. 循环结束仍未找到，返回-1。

多语言实现

class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if target == nums[mid]: return mid if nums[l] <= nums[mid]: if target > nums[mid] or target < nums[l]: l = mid + 1 else: r = mid - 1 else: if target < nums[mid] or target > nums[r]: r = mid - 1 else: l = mid + 1 return -1

class Solution { public int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while(l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return mid; } if (nums[l] <= nums[mid]) { if (target > nums[mid] || target < nums[l]) { l = mid + 1; } else { r = mid - 1; } } else { if (target < nums[mid] || target > nums [r]) { r = mid - 1; } else { l = mid + 1; } } } return -1; } }

class Solution { public: int search(std::vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (target == nums[mid]) { return mid; } if (nums[l] <= nums[mid]) { if (target > nums[mid] || target < nums[l]) { l = mid + 1; } else { r = mid - 1; } } else { if (target < nums[mid] || target > nums[r]) { r = mid - 1; } else { l = mid + 1; } } } return -1; } };

class Solution { /** * @param {number[]} nums * @param {number} target * @return {number} */ search(nums, target) { let l = 0, r = nums.length - 1; while (l <= r) { const mid = Math.floor((l + r) / 2); if (target === nums[mid]) { return mid; } if (nums[l] <= nums[mid]) { if (target > nums[mid] || target < nums[l]) { l = mid + 1; } else { r = mid - 1; } } else { if (target < nums[mid] || target > nums[r]) { r = mid - 1; } else { l = mid + 1; } } } return -1; } }

public class Solution { public int Search(int[] nums, int target) { int l = 0, r = nums.Length - 1; while (l <= r) { int mid = (l + r) / 2; if (target == nums[mid]) { return mid; } if (nums[l] <= nums[mid]) { if (target > nums[mid] || target < nums[l]) { l = mid + 1; } else { r = mid - 1; } } else { if (target < nums[mid] || target > nums[r]) { r = mid - 1; } else { l = mid + 1; } } } return -1; } }

func search(nums []int, target int) int { l, r := 0, len(nums)-1 for l <= r { mid := (l + r) / 2 if target == nums[mid] { return mid } if nums[l] <= nums[mid] { if target > nums[mid] || target < nums[l] { l = mid + 1 } else { r = mid - 1 } } else { if target < nums[mid] || target > nums[r] { r = mid - 1 } else { l = mid + 1 } } } return -1 }

class Solution { fun search(nums: IntArray, target: Int): Int { var l = 0 var r = nums.size - 1 while (l <= r) { val mid = (l + r) / 2 if (target == nums[mid]) { return mid } if (nums[l] <= nums[mid]) { if (target > nums[mid] || target < nums[l]) { l = mid + 1 } else { r = mid - 1 } } else { if (target < nums[mid] || target > nums[r]) { r = mid - 1 } else { l = mid + 1 } } } return -1 } }

class Solution { func search(_ nums: [Int], _ target: Int) -> Int { var l = 0, r = nums.count - 1 while l <= r { let mid = (l + r) / 2 if target == nums[mid] { return mid } if nums[l] <= nums[mid] { if target > nums[mid] || target < nums[l] { l = mid + 1 } else { r = mid - 1 } } else { if target < nums[mid] || target > nums[r] { r = mid - 1 } else { l = mid + 1 } } } return -1 } }

impl Solution { pub fn search(nums: Vec<i32>, target: i32) -> i32 { let (mut l, mut r) = (0i32, nums.len() as i32 - 1); while l <= r { let mid = (l + r) / 2; if target == nums[mid as usize] { return mid; } if nums[l as usize] <= nums[mid as usize] { if target > nums[mid as usize] || target < nums[l as usize] { l = mid + 1; } else { r = mid - 1; } } else { if target < nums[mid as usize] || target > nums[r as usize] { r = mid - 1; } else { l = mid + 1; } } } -1 } }

复杂度分析

• 时间复杂度：O(log n)，单次遍历即完成，无需额外的 pivot 搜索阶段。
• 空间复杂度：O(1)。

5. 仓库源码对照：单趟法实现细节

仓库中该题的参考实现与上述「单趟法」完全一致，可以直接对照阅读：

• Python 实现 —— 使用nums[l] <= nums[mid]判断左段是否有序，注释中明确标出# left sorted portion与# right sorted portion两个分支；
• Go 实现 —— 结构相同，同样以nums[left] <= nums[mid]区分左右段；
• Rust 实现 —— 需要注意 Rust 中l、r以i32声明，访问数组时通过as usize做索引转换；
• JavaScript 实现 —— 采用(left + right) >> 1位运算代替除法求中间索引，逻辑上等价；
• C 实现 —— 采用了「先找 pivot 再两段分别二分」的变体：findPivotIndex通过判断nums[m] > nums[m+1]/nums[m] < nums[m-1]直接定位拐点，随后在[0, pivot]与[pivot+1, n]两段上分别做标准binarySearch。

从源码结构看，Python/Go/Rust/JavaScript 等实现统一收敛为「单趟法」，说明这是社区与仓库中最推荐的写法：它不需要单独维护 pivot 变量，仅凭nums[l] <= nums[mid]判断当前有序段即可完成区间收缩，代码量更少、分支更清晰。

仓库中还提供了含重复元素的进阶版本（LeetCode 81 题）参考实现，如 Python 实现、Java 实现、Kotlin 实现，对应讲解见 search-in-rotated-sorted-array-ii.md。当数组中允许重复元素时，nums[l] == nums[mid]会破坏「某一段必然有序」的判定，需要退化为逐步移动l，这也是理解本题边界的重要延伸。

6. 常见陷阱

6.1 与左端元素比较时误用严格不等号

在单趟法中，判断左段有序的条件是nums[l] <= nums[mid]，必须使用<=而非<。当子数组很小、出现l == mid时（此时nums[l] == nums[mid]恒成立），若写成<会把有序的左段误判为右段，导致选错搜索半区、漏掉目标。

6.2 混淆「找 pivot」与「找 target」的逻辑

两趟法要求先找 pivot（最小元素索引），再在正确半段内找 target，两个步骤不能混为一谈：

• pivot 搜索依据nums[mid] > nums[r]决定移动方向；
• target 搜索是标准二分查找，依据nums[mid]与target的大小关系移动指针。

把两套判断条件混在一起写，会得到错误结果。

6.3 未处理未旋转（旋转 0 次）的数组

当数组没有旋转（或旋转 0 次）时，pivot 位于索引 0。解法必须在这种情况下依然正确。建议用[1, 2, 3, 4, 5]这类完全有序的数组做自测，确认：

• pivot 查找逻辑返回索引 0；
• 随后的目标搜索仍能正确工作（即落在[pivot, len-1]整段上二分）。

6.4 旋转点边界与mid计算溢出

在 C/C++/Java 等语言中，(l + r) / 2在数组极大时可能溢出。仓库 C 实现 中采用了s + (e - s) / 2的写法避免溢出；JavaScript 等语言则用Math.floor((l + r) / 2)或位运算>> 1保证整数语义。实际面试或工程中，推荐使用l + (r - l) / 2的形式。

7. 解法总览与延伸思考

复杂度对比

关键结论

• 旋转数组的查找之所以可以用二分，本质是因为它由两段有序子数组拼接而成，任意时刻都能确定至少一个有序半区（Hint 3/Hint 4 的观察），据此排除一半搜索空间。
• 「先找 pivot」与「单趟判断」是同一性质的两条实现路线：前者思路更直观、便于分段调试；后者代码更紧凑、无需单独维护 pivot。
• 未旋转数组是旋转数组的特例（pivot = 0），所有解法都应在该输入上保持正确。
• 若数组中存在重复元素，单趟法的nums[l] <= nums[mid]判定可能失效（nums[l] == nums[mid]时无法判断哪段有序），需要像 LeetCode 81 题那样退化处理，参考 search-in-rotated-sorted-array-ii.md 及对应多语言实现。

推荐练习路径

1. 先用暴力法写出正确基线，再逐步替换为二分实现，保证两种写法在小数组上结果一致；
2. 用「未旋转」「旋转一次」「旋转到中点」「目标不存在」「目标在 pivot 处」等边界用例做自测；
3. 在 Python、Go、Rust 等语言中分别实现单趟法，体会各语言在索引类型（如 Rust 的as usize转换）上的差异；
4. 进阶挑战：阅读 search-in-rotated-sorted-array-ii.md，理解重复元素如何破坏有序段判定，以及退化策略的时间复杂度变化（最坏 O(n)）。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode