搜索旋转排序数组(LeetCode 33)的二分思路
哪些公司问过
答案要点
- 旋转数组二分后至少一半有序,先判断 mid 落在哪段有序区间
- 左半有序时判断 nums[left]<=target<nums[mid],决定收缩方向
- 右半有序时判断 nums[mid]<target<=nums[right],决定收缩方向
- 时间复杂度 O(log n),空间复杂度 O(1)
- 边界:循环用 left<=right,判断有序要用 nums[left]<=nums[mid]
易错点
- nums[left]<=nums[mid] 漏掉等号,只剩两个元素时判断出错
- 区间判断开闭写错,导致 target 恰好等于端点时被漏掉
- 把同样写法套到有重复元素的数组上
面试官常见追问
- 有重复元素怎么办(LC81)?
- 如何找旋转数组的最小值(LC153)?
- 能先找旋转点再二分吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。