企业官网建设流程全解析

LeetCode-Go 题解：33. Search in Rotated Sorted Array 旋转数组二分查找实现解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode-Go 仓库中第 33 题「Search in Rotated Sorted Array」的题解文档为主线，深入讲解"升序数组在未知枢轴处旋转后，如何用 O(log n) 二分查找定位目标值"这一经典算法问题。你将掌握旋转数组的二分区间判定技巧、无重复与有重复两种场景的实现差异，并通过仓库内真实源码与测试用例验证算法正确性，最终能够独立实现并测试此类题目。

题目背景与核心要求

原题（33. Search in Rotated Sorted Array）的完整描述如下：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,[0,1,2,4,5,6,7]might become[4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return-1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order ofO(logn).

示例 1：

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

示例 2：

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

提炼出的关键约束有三点：

1. 原数组升序排列，且在某个未知枢轴处旋转；
2. 数组中不存在重复元素；
3. 算法时间复杂度必须为O(log n)级别。

正是因为第 3 点约束，线性扫描（O(n)）不可接受，必须借助"数组整体基本有序"的特性设计二分搜索。

解题思路：对"断开点"二分

旋转数组的结构特征

数组原本从小到大排列，现在把末尾随机一段有序序列搬到数组前面，从而形成前后两段各自升序的子序列。例如[0,1,2,4,5,6,7]旋转为[4,5,6,7,0,1,2]后：

• 前段[4,5,6,7]：数值相对较大；
• 后段[0,1,2]：数值相对较小；
• 两段之间有一个"断开点"，即 7 与 0 的衔接处。

虽然中间存在这个断开点，但每一段内部依然单调有序，这正是二分搜索能够继续发挥作用的前提。

区间归属判定：比较 nums[mid] 与两端点

设low、high、mid分别为左边界、右边界与中点，通过对nums[mid]与nums[low]、nums[high]的大小比较，可以判断mid落在哪一段：

• 若nums[mid] > nums[low]，说明mid落在数值较大的前段；
• 若nums[mid] <= nums[low]，说明mid落在数值较小的后段；
• 若nums[mid] < nums[high]，说明mid落在数值较小的后段；
• 若nums[mid] >= nums[high]，说明mid落在数值较大的前段。

另外，还存在nums[low] == nums[mid]与nums[high] == nums[mid]两个边界情形，需单独处理（仓库实现中以low++/high--的方式逐步收缩边界）。

收缩区间的决策逻辑

以 mid 所在段的单调性为基础，再结合 target 与段端点的比较决定向哪一侧收缩：

• mid 位于数值较大的前段时：前段[low..mid]严格单调递增。若nums[low] <= target < nums[mid]，则 target 只可能落在[low, mid-1]，令high = mid - 1；否则令low = mid + 1；
• mid 位于数值较小的后段时：后段[mid..high]严格单调递增。若nums[mid] < target <= nums[high]，则 target 只可能落在[mid+1, high]，令low = mid + 1；否则令high = mid - 1；
• 循环中若nums[mid] == target直接返回mid；
• 循环结束仍未命中，返回-1。

由于每一轮都能把搜索区间压缩约一半，整体时间复杂度为 O(log n)。

仓库源码实现详解

题解文档中的核心代码如下（对应仓库文件 leetcode/0033.Search-in-Rotated-Sorted-Array/33. Search in Rotated Sorted Array.go）：

package leetcode func search33(nums []int, target int) int { if len(nums) == 0 { return -1 } low, high := 0, len(nums)-1 for low <= high { mid := low + (high-low)>>1 if nums[mid] == target { return mid } else if nums[mid] > nums[low] { // 在数值大的一部分区间里 if nums[low] <= target && target < nums[mid] { high = mid - 1 } else { low = mid + 1 } } else if nums[mid] < nums[high] { // 在数值小的一部分区间里 if nums[mid] < target && target <= nums[high] { low = mid + 1 } else { high = mid - 1 } } else { if nums[low] == nums[mid] { low++ } if nums[high] == nums[mid] { high-- } } } return -1 }

对实现细节的逐一说明：

• 空数组守卫：函数入口处先判断len(nums) == 0，直接返回-1，避免对空切片执行下标访问；
• 中点计算：使用mid := low + (high-low)>>1而非(low+high)/2，既防止整型溢出，又通过右移一位完成除以 2 的运算；
• 循环条件：for low <= high保证区间为空时退出，此时未找到 target，返回-1；
• 区间归属判断的先后顺序：先判nums[mid] > nums[low]（大值段），再判nums[mid] < nums[high]（小值段），最后落入else处理nums[low] == nums[mid]或nums[high] == nums[mid]的退化情形；
• 边界处理：else分支中通过low++、high--各推进一步，逐步排除与nums[mid]相等的端点。这一防御性写法使得本实现即使在含有重复元素的数组上运行也具备一定容错能力（严格场景对应第 81 题）。

从函数命名可见，search33中的33是题目编号，遵循仓库"题号+题目名"的组织约定，与其它题解（如search81）相互独立、互不干扰。

测试用例与验证

仓库为本题提供了完整的表驱动测试，见 leetcode/0033.Search-in-Rotated-Sorted-Array/33. Search in Rotated Sorted Array_test.go。测试覆盖了以下典型场景：

测试框架使用question33/para33/ans33三个结构体组织用例：para33封装nums与target两个输入参数，ans33记录期望索引；Test_Problem33遍历全部用例，调用search33(p.nums, p.target)并与期望值比对，不一致时通过t.Fatalf立即失败。运行方式遵循仓库根目录 gotest.sh 中定义的测试命令：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该命令一次性对leetcode/...下所有包执行带覆盖率统计的测试，其中就包含本题所在包；项目覆盖率为 100% 的目标也正是通过此类完备用例来保障的。

延伸：与第 81 题（含重复元素）的关系

本题的进阶版本是 81. Search in Rotated Sorted Array II，区别仅在于数组可能包含重复元素，返回值从索引变为布尔值（存在返回true，否则返回false）。仓库该题 README 明确指出："这一题是第 33 题的加强版，实现代码完全一样，只不过输出变了"——即nums[low] == nums[mid]、nums[high] == nums[mid]时的low++/high--收缩策略正是为应对重复元素而保留的防御性逻辑。

需要指出的是：一旦引入重复元素，最坏情况下（例如数组全为同一元素）二分退化到线性扫描，时间复杂度上升为 O(n)；而第 33 题在无重复的前提下，各分支都保证收缩一半区间，始终严格保持 O(log n)。

总结

本题是"有序数组 + 旋转"类二分问题的经典范式，核心方法论可以沉淀为三步：

1. 识别结构：旋转数组由两段单调区间组成，单调性是二分的前提；
2. 定位区间：通过nums[mid]与nums[low]、nums[high]的关系判断 mid 处于大值段还是小值段；
3. 定向收缩：依据所在段的单调性，用 target 与段端点的比较决定搜索方向，逐轮减半区间。

掌握这一思路后，可顺势完成第 81 题（含重复元素）、第 153/154 题（寻找旋转数组最小值）等一系列同族题目，它们共享同一套区间判定框架。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go