旋转排序数组中找最小值(含重复元素)
哪些公司问过
答案要点
- 旋转数组由两段递增序列组成,最小值是第二段的起点
- 二分时与右端比较:mid 值大于 right 值则 left=mid+1,小于则 right=mid
- 与左端比较在数组未旋转时会判断错误,所以通常与右端比较
- 有重复时 mid 值等于 right 值无法判断方向,执行 right 减 1 收缩
- 无重复 O(log n),有重复最坏 O(n);若要求下标需注意重复值时返回哪个位置
易错点
- 用 nums[mid] 和 nums[left] 比较,未旋转数组会得出错误结果
- 有重复元素时直接套无重复的二分,例如 [1,1,1,0,1] 会出错
- right=mid 却用 left<=right 做循环条件,导致死循环
面试官常见追问
- 有重复时要求返回最小值第一次出现的下标怎么办?
- 在旋转数组里查找某个目标值怎么做?
- 为什么循环条件是 left < right 而不是小于等于?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。