知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 搜索旋转排序数组 ## 题目(LeetCode 33) 在一个旋转过的有序数组中搜索 target,返回下标,找不到返回 -1。 ``` 输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4 输入:nums = [4,5,6,7,0,1,2], target = 3 输出:-1 ``` 要求 O(log n) 时间。 ## 大白话理解 正常的二分查找需要**全局有序**,但旋转数组打破了全局有序。 不过仔细观察:旋转数组 = 两个有序片段拼在一起。 ``` 原数组:[0, 1, 2, 4, 5, 6, 7] 旋转后:[4, 5, 6, 7, 0, 1, 2] └─前半有序──┘ └─后半有序──┘ ``` 每次取 mid,**至少有一半是有序的**。利用有序的那一半来判断 target 在不在里面,就可以决定丢哪一半。 ``` 每次二分: 1. 判断左半还是右半有序 2. 在有序的那一半里判断 target 在不在 3. 在就搜那一半,不在就搜另一半 ``` 想象一本被打乱章节的书,你把书从中间翻开,虽然整本书顺序乱了,但翻开的那一半至少有一段内容是按顺序排列的。通过判断你要找的内容在这段有序内容里还是外面,就能决定翻左边还是右边。 ## 代码 ```java public int search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) { return mid; // 命中 } // 判断哪一半是有序的 if (nums[l] <= nums[mid]) { // 情况 A:左半有序 [l, mid] // [4, 5, 6, 7, 0, 1, 2] // l mid r // └─有序─┘ if (nums[l] <= target && target < nums[mid]) { r = mid - 1; // target 在左半 → 搜左边 } else { l = mid + 1; // target 不在左半 → 搜右边 } } else { // 情况 B:右半有序 [mid, r] // [4, 5, 6, 7, 0, 1, 2] // mid r // └─有序──┘ if (nums[mid] < target && target <= nums[r]) { l = mid + 1; // target 在右半 → 搜右边 } else { r = mid - 1; // target 不在右半 → 搜左边 } } } return -1; // 没找到 } ``` ## 核心逻辑图解 ``` 旋转数组结构: ┌────────────────────────────────────┐ │ 大值区域 │ 小值区域 │ │ [4, 5, 6, 7] │ [0, 1, 2] │ │ 递增 │ 递增 │ └────────────────────────────────────┘ ↑ ↑ 左半可能跨过断裂点 右半可能跨过断裂点 关键判断:nums[l] <= nums[mid]? - 是 → 左半 [l,mid] 连续,没有断裂点 - 否 → 右半 [mid,r] 连续,断裂点在左边 ``` ``` 为什么 nums[l] <= nums[mid] 能判断左半有序? 情况1:旋转点不在 [l,mid] 内 [4, 5, 6, 7, 0, 1, 2] l mid r l→mid 递增 → nums[l]=4, nums[mid]=6 → nums[l] <= nums[mid] ✓ 情况2:旋转点在 [l,mid] 内 [7, 0, 1, 2, 4, 5, 6] l mid r l→mid 先降后升 → nums[l]=7, nums[mid]=1 → nums[l] > nums[mid] ✗ 此时 mid→r 反而是连续递增的 ``` ## 过程模拟 ``` nums = [4, 5, 6, 7, 0, 1, 2], target = 0 第1轮: l=0, r=6, mid=3 → nums[3]=7 nums[3]=7 ≠ 0,继续 nums[l]=4 <= nums[mid]=7 → 左半有序 [4,5,6,7] target=0 在 [4, 7) 中?→ No(0 < 4) → 搜右边 l=mid+1=4 [4, 5, 6, 7, 0, 1, 2] └─有序──┘ └待搜──┘ ↑ l=4 第2轮: l=4, r=6, mid=5 → nums[5]=1 nums[5]=1 ≠ 0,继续 nums[l]=0 <= nums[mid]=1 → 左半有序 [0,1] target=0 在 [0, 1) 中?→ Yes(0 <= 0 < 1) → 搜左边 r=mid-1=4 [4, 5, 6, 7, 0, 1, 2] └有序┘ ↑ l=4,r=4 第3轮: l=4, r=4, mid=4 → nums[4]=0 nums[4]=0 == target → 返回 4 ✓ 答案:4 ``` ## 另一种模拟:target 不存在的情况 ``` nums = [4, 5, 6, 7, 0, 1, 2], target = 3 第1轮: l=0, r=6, mid=3 → nums[3]=7 nums[l]=4 <= nums[mid]=7 → 左半有序 [4,5,6,7] target=3 在 [4, 7) 中?→ No → l=4 第2轮: l=4, r=6, mid=5 → nums[5]=1 nums[l]=0 <= nums[mid]=1 → 左半有序 [0,1] target=3 在 [0, 1) 中?→ No → l=6 第3轮: l=6, r=6, mid=6 → nums[6]=2 nums[l]=2 <= nums[mid]=2 → 左半有序 [2] target=3 在 [2, 2) 中?→ No → l=7 l=7, r=6 → l > r 退出,返回 -1 ✓ ``` ## 复杂度 - 时间:O(log n),每轮砍掉一半 - 空间:O(1) ## 为什么是 O(log n)? 虽然数组被旋转了,但我们每次还是砍掉一半搜索空间: - 先判断哪半有序 → O(1) - 再判断 target 在不在有序半区 → O(1) - 在就搜有序半区,不在就搜另一半 → 总是砍半 ## 一句话总结 旋转数组二分的关键:每次判断哪半有序,再利用有序半区的边界判断 target 在哪一半。 --- 上一篇:[01 - 二分查找模板](./01-template.md) | 下一篇:[03 - 寻找旋转数组最小值](./03-find-min-rotated.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入