[特殊字符] 旋转排序数组中的高效搜索：从线性到二分查找的进阶之路

给定一个由不同元素构成的旋转排序数组原本是升序排列但在某个未知点进行了旋转要求快速找到目标元素的索引。如果不存在则返回 -1。示例 1输入arr [5, 6, 7, 8, 9, 10, 1, 2, 3],key 3输出8示例 2输入arr [3, 5, 1, 2],key 6输出-1示例 3输入arr [33, 42, 72, 99],key 42输出1目录朴素解法线性搜索 - O(n) 时间 O(1) 空间期望解法一两次二分查找 - O(log n) 时间 O(1) 空间期望解法二单次二分查找 - O(log n) 时间 O(1) 空间1. 朴素解法线性搜索最直接的方式就是遍历整个数组逐个元素与目标值比较。找到则返回索引否则返回 -1。复杂度分析时间复杂度O(n) —— 最坏情况下需要检查所有元素。空间复杂度O(1) —— 只用了常数个变量。代码示例Pythondefsearch(arr,key):foriinrange(len(arr)):ifarr[i]key:returnireturn-1虽然简单但效率不高。当数组很大时线性搜索会非常慢。接下来我们看看如何利用旋转排序数组的特性来加速。说到旋转排序数组的二分查找很多人卡在“如何判断哪半有序”这个点上。死磕代码不如亲眼看到指针如何移动——强烈安利一个叫图码的网站它把60多种算法做成交互式动画你可以自己输入测试数据甚至上传C/C/Java/Python代码看着代码一行行跑出动画。这个工具专门为408考研和数据结构期末考试设计全书级知识点可运行代码遇到不懂的还能7x24小时选中代码让AI解释。学算法可视化上图码就对了。图码-数据结构与算法交互式可视化平台访问网站https://totuma.cn2. 期望解法一两次二分查找核心思路是先找到数组中**最小元素即旋转点**的索引这样就把原数组分成了两个有序的子数组。然后根据目标值与第一个元素的大小关系决定在哪个子数组上进行标准的二分查找。步骤详解找到最小元素的索引pivot旋转点。如果arr[pivot] key直接返回pivot。如果pivot 0说明整个数组是未旋转的直接对整个数组做二分查找。否则比较key和arr[0]若key arr[0]则在左半部分[0, pivot-1]进行二分查找。否则在右半部分[pivot1, n-1]进行二分查找。复杂度分析时间复杂度O(log n) —— 两次二分查找每次都是 O(log n)。空间复杂度O(1) —— 只用了常数个变量。代码示例PythondefbinarySearch(arr,lo,hi,x):whilelohi:midlo(hi-lo)//2ifarr[mid]x:returnmidifarr[mid]x:lomid1else:himid-1return-1deffindPivot(arr,lo,hi):whilelohi:ifarr[lo]arr[hi]:returnlo mid(lohi)//2ifarr[mid]arr[hi]:lomid1else:himidreturnlodefsearch(arr,key):nlen(arr)pivotfindPivot(arr,0,n-1)ifarr[pivot]key:returnpivotifpivot0:returnbinarySearch(arr,0,n-1,key)ifarr[0]key:returnbinarySearch(arr,0,pivot-1,key)returnbinarySearch(arr,pivot1,n-1,key)输出83. 期望解法二单次二分查找更优雅的做法是直接对旋转数组进行一次修改过的二分查找。在每一次迭代中我们检查中间元素arr[mid]是否等于目标值。如果不是我们就判断左半部分还是右半部分是有序的然后根据目标值是否落在该有序区间内来调整搜索范围。算法流程初始化lo 0,hi n-1。当lo hi时计算mid lo (hi - lo) // 2。如果arr[mid] key返回mid。判断左半部分是否有序arr[mid] arr[lo]。如果左半部分有序且key在[arr[lo], arr[mid])范围内则hi mid - 1否则lo mid 1。否则右半部分有序如果key在(arr[mid], arr[hi]]范围内则lo mid 1否则hi mid - 1。如果循环结束未找到返回 -1。复杂度分析时间复杂度O(log n) —— 每次迭代将搜索范围缩小一半。空间复杂度O(1) —— 只用了常数个变量。代码示例Pythondefsearch(arr,key):lo,hi0,len(arr)-1whilelohi:midlo(hi-lo)//2ifarr[mid]key:returnmid# 左半部分有序ifarr[mid]arr[lo]:ifkeyarr[lo]andkeyarr[mid]:himid-1else:lomid1# 右半部分有序else:ifkeyarr[mid]andkeyarr[hi]:lomid1else:himid-1return-1输出8总结解法时间复杂度空间复杂度说明线性搜索O(n)O(1)简单但慢两次二分O(log n)O(1)先找旋转点再二分单次二分O(log n)O(1)直接修改二分查找逻辑推荐使用单次二分查找因为它代码更简洁且不需要额外寻找旋转点。掌握旋转排序数组的搜索不仅能应对面试题更能加深对二分查找变体的理解。下次遇到类似问题记得试试这个技巧哦