搜索旋转排序数组
Search in Rotated Sorted Array
本机进度仅保存在当前浏览器
题目描述
升序数组在某个未知下标处发生旋转（如 [0,1,2,4,5,6,7] 旋转后变为 [4,5,6,7,0,1,2]），在数组中搜索 target，返回下标或 -1。要求 O(log n)。
示例：nums = [4, 5, 6, 7, 0, 1, 2]，target = 0，输出 4。
解题思路
- 旋转数组的关键性质：从中点切开，左右两半至少有一半是完全有序的。
- 判断 nums[l] <= nums[mid] 即可确定左半是否有序，再判断 target 是否落在该有序区间内。
- 若 target 在有序半段内则收缩到那一半，否则去另一半；每步仍淘汰一半，保持 O(log n)。
- 注意 l == mid 的退化情况（区间仅剩一两个元素），用 <= 保证判断正确。
参考实现
查看参考实现Python · 建议先自行作答
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]:
# 左半段有序
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
# 右半段有序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1