- 正确答案：在旋转有序数组中查找目标值，应使用修改版的二分查找算法，时间复杂度O(log n)，空间复杂度O(1)。核心思想是利用“旋转数组中至少有一半子区间必然是单调有序”的性质，在每次二分时判断哪一半有序，并据此决定是否能在该半区中排除目标值。 - 解答思路： 1. 初始化左右指针 left = 0, right = n-1； 2. 循环条件为 left <= right； 3. 计算 mid = left + (right - left) / 2； 4. 若 nums[mid] == target，直接返回 mid； 5. 否则判断哪一侧是有序区间： - 若 nums[left] <= nums[mid]，说明左半段 [left, mid] 有序（注意等号处理边界，如单元素或无旋转情况）； → 进一步判断 target 是否落在该有序区间内：若 nums[left] <= target < nums[mid]，则搜索左半段（right = mid - 1），否则搜索右半段（left = mid + 1）； - 否则（即 nums[mid] < nums[left]），说明右半段 [mid, right] 有序； → 判断 target 是否落在该区间：若 nums[mid] < target <= nums[right]，则搜索右半段（left = mid + 1），否则搜索左半段（right = mid - 1）； 6. 循环结束未找到，返回 -1。 - 深度知识讲解：本题考察对二分查找本质的深刻理解——它不依赖“整体有序”，而依赖“可判定性”和“单向排除性”。旋转有序数组虽整体无序，但任意中点将数组划分为两部分，其中必有一部分严格单调递增（数学证明：设原数组升序，旋转点k∈[0,n)，则数组形如 [A[k],...,A[n-1],A[0],...,A[k-1]]；对任意mid，若mid < k，则左段跨断点不单调，但右段 [mid, n-1] 包含后缀升序段+可能前缀，需验证；更严谨的观察是：nums[left] 和 nums[mid] 的大小关系直接反映 left→mid 是否未跨越旋转点——即是否保持升序）。关键底层细节： • 为什么用 nums[left] <= nums[mid] 判断左段有序？因为旋转数组由两个升序段拼接而成，若 left 到 mid 未跨越旋转点，则该段完全位于某一段升序内，故有序；一旦跨越（即旋转点 ∈ (left, mid)），则 nums[left] > nums[mid]（例如 [4,5,6,7,0,1,2]，left=0→4，mid=3→7，4<=7，左段有序；若 left=4→0，mid=5→1，0>1，左段跨断点，无序）。 • 边界处理必须包含等号：当 nums[left] == nums[mid] 时（如 [1,1,1,0,1] 或 [1,0,1,1,1]），无法确定哪边有序（存在重复元素干扰），此时最坏退化为线性扫描；但题目若明确“无重复元素”，则 nums[left] == nums[mid] 仅在 left==mid 时成立，无需特殊处理。本题通常默认无重复，故可安全使用 <=。 • 与标准二分的区别：标准二分仅靠 target 与 nums[mid] 比较缩小区间；本题需先通过 nums[left]/nums[mid]/nums[right] 的大小关系推断有序侧，再结合 target 与有序侧端点比较做决策——本质是“二分 + 区间性质推理”。 - 代码示例（Python风格伪代码，无重复元素）： ``` def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid # 判断左半段是否有序 if nums[left] <= nums[mid]: # 左段有序，检查target是否在左段范围内 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 ``` - 扩展知识： • 若数组含重复元素（如 LeetCode 81 题），当 nums[left] == nums[mid] == nums[right] 时，无法判断旋转点位置，此时需 left++, right-- 缩小范围，最坏时间复杂度退化为 O(n)。 • 可推广至“找旋转点”（最小值位置）：只需比较 nums[mid] 与 nums[right]，若 nums[mid] > nums[right]，旋转点在右半段，否则在左半段（含mid）。 • 底层内存视角：该算法充分利用 CPU 局部性——访问 nums[left], nums[mid], nums[right] 三个离散地址，但现代缓存行（通常64字节）大概率一次性加载相邻元素，实际性能优于理论分析。 • 工程实践提醒：真实系统中若数组极大且随机访问慢（如磁盘映射文件），可考虑块状二分或预取优化，但面试中聚焦逻辑正确性与复杂度即可。

27日常实习 小红书后端二面 40min

全站热榜

创作者周榜

27日常实习小红书后端二面 40min