- 正确答案：LeetCode 第 33 题“搜索旋转排序数组”要求在经过一次旋转的有序数组中查找目标值，返回其索引，若不存在则返回 -1。该数组是将一个升序排列的整数数组在某个未知位置进行旋转（例如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]）。解决此题的最优方法是一次二分查找，在每次二分过程中判断哪一半是有序的，并根据目标值是否落在该有序区间决定搜索方向。 - 解答思路： 1. 使用标准二分查找框架，定义 left = 0，right = n - 1。 2. 在每一步中计算 mid = (left + right) / 2，检查 nums[mid] 是否等于 target，如果是，直接返回 mid。 3. 判断从 left 到 mid 是否为有序段（即 nums[left] <= nums[mid]），或者 mid 到 right 是否为有序段（即 nums[mid] <= nums[right]）。 - 注意：由于存在重复元素或边界情况，必须使用 <= 而不是 <。 4. 若左半段有序，则判断 target 是否落在 [nums[left], nums[mid]) 区间内，若是则搜索左半边；否则搜索右半边。 5. 若右半段有序，则判断 target 是否落在 (nums[mid], nums[right]] 区间内，若是则搜索右半边；否则搜索左半边。 6. 持续缩小范围直到找到目标或 left > right。关键点在于：虽然整个数组不是有序的，但每次二分后，至少有一半是有序的。我们可以利用这一性质进行有效剪枝。 - 深度知识讲解：本题考察的是对二分查找本质的理解——不仅仅是用于“完全有序”数组，而是适用于“局部有序 + 可判断搜索方向”的场景。核心思想是“二分不等于必须全局有序”，只要能在 O(1) 时间内判断出某一部分是否包含目标值即可。数据结构层面，输入是一个旋转后的有序数组，本质上属于“循环有序数组”（Circularly Sorted Array）。这类数组具有如下性质： - 存在一个分界点（pivot），使得前半段和后半段各自有序。 - 最小值的位置即为旋转点。 - 对任意中点 mid，left ~ mid 和 mid ~ right 至少有一个区间是单调递增的。实现原理上，我们不需要显式地先找旋转点（如你最初做法：两次二分，第一次找最小值位置，第二次确定在哪一段再二分查找），那样时间复杂度仍是 O(log n)，但常数更大且代码更复杂。而一次二分的方法通过每次判断有序区间来隐式处理旋转结构，效率更高、逻辑更紧凑。常见错误包括： - 忽略等号导致边界错误（如用 < 而不用 <=） - 区间开闭处理不当（比如把 target == nums[left] 错误排除） - 没意识到“一定有一半有序”这个关键性质时间复杂度：O(log n)，每次迭代都将搜索空间减半。空间复杂度：O(1) - 扩展知识点： 1. 类似题目： - LeetCode 81：允许重复元素的旋转数组查找（需处理 nums[left] == nums[mid] == nums[right] 的情况，可能退化到 O(n)） - LeetCode 153：寻找旋转排序数组中的最小值（只需找 pivot） - LeetCode 154：含重复元素的最小值查找 2. 应用场景：实际系统中某些日志文件按时间排序但因滚动而“断开”，形成类似结构，可用此类方法快速定位。 3. 更高阶变种：二维旋转矩阵、多段旋转数组等。 - 代码示例（Python）： ``` def search(nums, target): if not nums: return -1 left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 判断左半部分是否有序 if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # 否则右半部分一定有序 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1 ``` 解释说明： - 条件 nums[left] <= nums[mid] 表示左半段有序（注意等于的情况，当 left == mid 或有重复时可能发生） - 若左半段有序，再判断 target 是否在 [nums[left], nums[mid]) 内（左闭右开），是则去左边，否则去右边 - 否则右半段有序，判断 target 是否在 (nums[mid], nums[right]] 内（左开右闭），是则去右边，否则去左边这个写法避免了显式找 pivot，充分利用了“每次二分必有一半有序”的特性，实现了一次二分完成搜索的目标。面试建议：当你遇到“旋转”、“部分有序”、“断点未知”等关键词时，应立刻联想到“局部有序 + 二分判定”的策略，优先思考能否通过判断区间有序性来指导搜索方向，而不是强行恢复原始顺序或多次扫描。

拼多多二面

全站热榜

创作者周榜