旋转数组的最小数字 - JZ06

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在重复元素值的数组 numbers，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。

示例：

输入: [3,4,5,1,2]
输出: 1

输入: [2,2,2,0,1]
输出: 0

输入: [1,3,5]
输出: 1

解题思路

这道题是二分查找的经典应用，但需要处理重复元素的特殊情况：

核心思想：

1. 旋转数组可以看作两个有序数组的拼接
2. 最小元素是第二个有序数组的第一个元素
3. 使用二分查找定位最小元素

算法步骤：

1. 设置左右指针 left 和 right
2. 计算中间位置 mid
3. 比较 numbers[mid] 与 numbers[right]：
   • 如果 numbers[mid] < numbers[right]：最小值在左半部分（包括mid）
   • 如果 numbers[mid] > numbers[right]：最小值在右半部分
   • 如果 numbers[mid] == numbers[right]：无法确定，只能 right--

关键点：

• 为什么比较 numbers[mid] 和 numbers[right]？
• 如何处理重复元素？
• 边界条件的处理

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 工具函数定义
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现：

• minArray(numbers []int) int - 主要实现
• minArrayBinarySearch(numbers []int) int - 二分查找版本
• minArrayLinear(numbers []int) int - 线性搜索版本（对比）

2. 运行测试

go test -v
go test -bench=.

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
二分查找	O(log n) ~ O(n)	O(1)	最坏情况全是重复元素
线性搜索	O(n)	O(1)	简单但不够优化

知识点

• 二分查找
• 旋转数组性质
• 重复元素处理
• 边界条件判断
• 算法优化思想