当前位置：首页 > news >正文

二分查找篇——搜索旋转排序数组【LeetCode】一次二分查找

news 2025/7/17 9:30:20

33. 搜索旋转排序数组

一、算法逻辑（逐步通顺讲解每一步思路）

本题的输入是一个被旋转的升序数组 nums（无重复元素），我们要返回目标值 target 的下标，不存在则返回 -1。
这段代码的思路属于“自适应二分查找”：不显式地找出旋转点，而是通过构造判断逻辑 check(i)，直接决定二分时该舍弃哪一侧。

✅ 1️⃣ 核心函数 `check(i)`：判断 `nums[i]` 是否“足够大”

函数逻辑分两种情况讨论当前值 nums[i] 相对于旋转点的位置（通过 nums[-1] 即最后一位判断）：

if x > nums[-1]:# 说明 x 在第一段（旋转点左边），我们只保留：# 情况 1：target 也在第一段，并且 x >= targetreturn target > nums[-1] and x >= target
else:# x 在第二段，我们只保留：# 情况 2：target 在第一段（目标比最后一个值大）# 情况 3：target 在第二段，并且 x >= targetreturn target > nums[-1] or x >= target

该判断本质上模拟了对两个段的划分，并控制搜索落在目标段内的区间中。

✅ 2️⃣ 二分搜索框架（偏左写法）

left = -1
right = len(nums) - 1

二分搜索区间为开区间 (left, right]
循环条件为 left + 1 < right
每轮检查 mid = (left + right) // 2 是否满足 check(mid)：
- 若满足，收缩右边界 right = mid
- 否则丢弃左半边，更新 left = mid

✅ 3️⃣ 返回结果

循环结束后，right 是最有可能的候选位置，再判断是否真的匹配：

return right if nums[right] == target else -1

二、核心点总结

✅ 本算法的关键亮点是：

利用 nums[-1] 作为旋转点分界参考，将数组划分为两段；
构造统一判断函数 check(i)，将“是否保留右边界”问题变成布尔表达式；
避免显式找出旋转点，实现了逻辑一体化的高效搜索；
使用 (left, right] 开区间 + 偏左二分模板，使边界处理清晰准确。

✅ 可视为「旋转数组查找 + lower_bound」的融合模板。

class Solution:def search(self, nums: List[int], target: int) -> int:def check(i: int) -> bool:x = nums[i]if x > nums[-1]:return target > nums[-1] and x >= targetreturn target > nums[-1] or x >= targetleft, right = -1, len(nums) - 1  # 开区间 (-1, n-1)while left + 1 < right:  # 开区间不为空mid = (left + right) // 2if check(mid):right = midelse:left = midreturn right if nums[right] == target else -1