旋转排序数组中的目标查找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。多语言实现class Solution: def search(self, nums: List[int], target: int) - int: for i in range(len(nums)): if nums[i] target: return i return -1class 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(vectorint 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: Veci32, target: i32) - i32 { for i in 0..nums.len() { if nums[i] target { return i as i32; } } -1 } }复杂度分析时间复杂度O(n)最坏情况下要扫描整个数组。空间复杂度O(1)只使用了常量级的额外空间。2. 二分查找先找旋转点Pivot直觉旋转后的有序数组本质上是两个有序子数组拼接在一起。核心思路分两步找到旋转点pivot——即最小元素的索引它标记了数组是在哪里发生旋转的。找到 pivot 之后数组被切分为左边一段有序子数组右边一段有序子数组。判断目标可能落在哪一段然后在该段上执行标准二分查找。两次二分合起来就能在对数时间内完成查找。这也与 hints/find-target-in-rotated-sorted-array.md 中 Hint 2 的思路一致例如[3, 4, 1, 2]是旋转两次的结果可以切分为两个有序段[3, 4]和[1, 2]只要找到这个「拐点」cut就可以分别在两段上二分。算法流程用二分查找定位pivot比较中间元素与最右元素。若nums[mid] nums[right]说明 pivot 在右半段。否则pivot 在左半段含mid位置。确定 pivot 后pivot 之前的子数组是一个有序段从 pivot 开始的子数组是另一个有序段。先在左半段执行标准二分查找找到则返回索引。否则在右半段执行标准二分查找。两段都找不到返回-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(vectorint 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(vectorint 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: Veci32, 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直觉旋转后的数组就是「两个有序数组粘在一起」因此可以把问题拆成两次简单的二分查找第一次二分找到 pivot——最小元素的索引即旋转发生的位置。第二次二分判断目标落在哪个有序段然后只在该段上执行标准二分。与上一节方案相比区别在于不两段都搜先通过 pivot 处的值与数组首尾值的关系一次性确定目标所在的段只搜一段。算法流程二分定位pivot比较中间元素与右端元素。若nums[mid] nums[right]pivot 在右侧。否则pivot 在左侧含mid位置。找到 pivot 后若target落在[nums[pivot], nums[最后]]区间内搜索右半段否则搜索左半段。在选定的半段上执行标准二分查找。找到返回索引否则返回-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 -1public 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(vectorint 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: Veci32, 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 与区间端点的关系决定收缩方向。算法流程初始化l 0, r len(nums) - 1。循环条件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。循环结束仍未找到返回-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 -1class 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::vectorint 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: Veci32, 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[m1]/nums[m] nums[m-1]直接定位拐点随后在[0, pivot]与[pivot1, 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. 解法总览与延伸思考复杂度对比解法时间空间核心思想暴力扫描O(n)O(1)逐个比较无视数组有序性二分找 pivot 两段分别搜O(log n)O(1)先定位最小元素索引再在两段上各做一次二分二分两趟法O(log n)O(1)找 pivot 后只搜目标所在的那一段二分单趟法O(log n)O(1)利用「至少一段有序」的性质单次收缩区间关键结论旋转数组的查找之所以可以用二分本质是因为它由两段有序子数组拼接而成任意时刻都能确定至少一个有序半区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 及对应多语言实现。推荐练习路径先用暴力法写出正确基线再逐步替换为二分实现保证两种写法在小数组上结果一致用「未旋转」「旋转一次」「旋转到中点」「目标不存在」「目标在 pivot 处」等边界用例做自测在 Python、Go、Rust 等语言中分别实现单趟法体会各语言在索引类型如 Rust 的as usize转换上的差异进阶挑战阅读 search-in-rotated-sorted-array-ii.md理解重复元素如何破坏有序段判定以及退化策略的时间复杂度变化最坏 O(n)。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
旋转排序数组中的目标查找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。多语言实现class Solution: def search(self, nums: List[int], target: int) - int: for i in range(len(nums)): if nums[i] target: return i return -1class 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(vectorint 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: Veci32, target: i32) - i32 { for i in 0..nums.len() { if nums[i] target { return i as i32; } } -1 } }复杂度分析时间复杂度O(n)最坏情况下要扫描整个数组。空间复杂度O(1)只使用了常量级的额外空间。2. 二分查找先找旋转点Pivot直觉旋转后的有序数组本质上是两个有序子数组拼接在一起。核心思路分两步找到旋转点pivot——即最小元素的索引它标记了数组是在哪里发生旋转的。找到 pivot 之后数组被切分为左边一段有序子数组右边一段有序子数组。判断目标可能落在哪一段然后在该段上执行标准二分查找。两次二分合起来就能在对数时间内完成查找。这也与 hints/find-target-in-rotated-sorted-array.md 中 Hint 2 的思路一致例如[3, 4, 1, 2]是旋转两次的结果可以切分为两个有序段[3, 4]和[1, 2]只要找到这个「拐点」cut就可以分别在两段上二分。算法流程用二分查找定位pivot比较中间元素与最右元素。若nums[mid] nums[right]说明 pivot 在右半段。否则pivot 在左半段含mid位置。确定 pivot 后pivot 之前的子数组是一个有序段从 pivot 开始的子数组是另一个有序段。先在左半段执行标准二分查找找到则返回索引。否则在右半段执行标准二分查找。两段都找不到返回-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(vectorint 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(vectorint 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: Veci32, 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直觉旋转后的数组就是「两个有序数组粘在一起」因此可以把问题拆成两次简单的二分查找第一次二分找到 pivot——最小元素的索引即旋转发生的位置。第二次二分判断目标落在哪个有序段然后只在该段上执行标准二分。与上一节方案相比区别在于不两段都搜先通过 pivot 处的值与数组首尾值的关系一次性确定目标所在的段只搜一段。算法流程二分定位pivot比较中间元素与右端元素。若nums[mid] nums[right]pivot 在右侧。否则pivot 在左侧含mid位置。找到 pivot 后若target落在[nums[pivot], nums[最后]]区间内搜索右半段否则搜索左半段。在选定的半段上执行标准二分查找。找到返回索引否则返回-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 -1public 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(vectorint 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: Veci32, 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 与区间端点的关系决定收缩方向。算法流程初始化l 0, r len(nums) - 1。循环条件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。循环结束仍未找到返回-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 -1class 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::vectorint 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: Veci32, 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[m1]/nums[m] nums[m-1]直接定位拐点随后在[0, pivot]与[pivot1, 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. 解法总览与延伸思考复杂度对比解法时间空间核心思想暴力扫描O(n)O(1)逐个比较无视数组有序性二分找 pivot 两段分别搜O(log n)O(1)先定位最小元素索引再在两段上各做一次二分二分两趟法O(log n)O(1)找 pivot 后只搜目标所在的那一段二分单趟法O(log n)O(1)利用「至少一段有序」的性质单次收缩区间关键结论旋转数组的查找之所以可以用二分本质是因为它由两段有序子数组拼接而成任意时刻都能确定至少一个有序半区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 及对应多语言实现。推荐练习路径先用暴力法写出正确基线再逐步替换为二分实现保证两种写法在小数组上结果一致用「未旋转」「旋转一次」「旋转到中点」「目标不存在」「目标在 pivot 处」等边界用例做自测在 Python、Go、Rust 等语言中分别实现单趟法体会各语言在索引类型如 Rust 的as usize转换上的差异进阶挑战阅读 search-in-rotated-sorted-array-ii.md理解重复元素如何破坏有序段判定以及退化策略的时间复杂度变化最坏 O(n)。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
