如何在旋转有序数组中查找目标值或最小值?
哪些公司问过
答案要点
- 二分查找,每次至少有一半是有序的
- 查目标:比较 nums[left] 与 nums[mid] 判断哪半有序,再看目标是否在有序区间内
- 有重复元素时首尾与中点相等无法判断,left++ 收缩,最坏 O(n)
- 找最小值:比较 nums[mid] 和 nums[right] 决定收缩方向
- 无重复时 O(log n),注意区间开闭和边界更新
易错点
- 判断有序半段时用小于而不是小于等于,left 与 mid 重合时出错
- 找最小值时 right 写成 mid-1,可能跳过最小值
- 有重复元素时仍然声称 O(log n)
面试官常见追问
- 找最小值时为什么和右端点比较,而不是左端点?
- 如何找到旋转点的位置?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。