北京
在技术面试中，旋转排序数组的搜索是一道经典题目。给定一个原本升序排列、但经过旋转的数组，要求在对数时间内找出目标元素的位置。如果不存在，返回-1。
最直接的思路是暴力扫描：从左到右逐个对比，找到目标就返回下标。代码实现只需要一个for循环，时间复杂度O(N)，空间复杂度O(1)。但这种方法完全忽略了数组本身的排序特性，面试官通常会追问更优解。
标准的二分查找要求数组完全有序，而旋转数组整体并不满足这个条件。以[4,5,6,7,0,1,2]为例，4到7是升序，0到2也是升序，但7到0出现了断崖。直接套用普通二分查找会得出错误结果。
关键观察在于：对于任意一个中间位置，至少有一半区间是严格有序的。用上面的例子，取中间元素7，左侧[4,5,6,7]是排序好的；取1时，左侧[0,1]同样有序。这个性质每轮迭代都成立。
算法流程分成两步走。先判断哪一半有序：如果左端点值小于等于中间值，说明左半有序；否则右半有序。然后在有序的那一半里检查目标值是否落在范围内——左半的条件是左端点≤目标<中间值，右半的条件是中间值<目标≤右端点。落在范围内就收缩到这一半继续搜索，否则收缩到另一半。
具体执行一遍：数组[4,5,6,7,0,1,2]，目标0。第一轮中间值是7，左半[4-7]有序但0不在其间，转向右半。第二轮中间值1，左半[0,1]有序且0在其中，收缩到左半。第三轮中间值恰好是0，返回下标4。
时间复杂度O(log N)，每一轮能稳定排除一半的搜索空间。空间复杂度O(1)，只用了几个指针变量。这个解法在面试中的一句话总结是：旋转排序数组中至少有一半始终有序，找准这一半并判断目标是否在其中，即可实现对数级别的裁剪。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
