Search in Rotated Sorted Array
一个由互不相同的整数组成的列表先按升序排列，然后进行了旋转：从列表开头取出任意数量的元素（也可以不取），并按原顺序移到列表末尾。例如，[2, 5, 8, 11, 15, 19, 23]旋转 4 位后变为[15, 19, 23, 2, 5, 8, 11]。给你旋转后的列表nums和一个整数target。请返回target在nums中的索引（从 0 开始计数）；如果不存在，则返回-1。要求时间复杂度为O(log n)。
函数
- numsinteger-array
- 旋转后的不重复整数列表
- targetinteger
- 要查找的值
- 返回值integer
- target 在 nums 中的索引；如果不存在，则为 -1
约束条件
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- 所有
nums中的值都不相同。 nums是一个递增列表，经过了某个k值的旋转，其中0 ≤ k < nums.length；k = 0表示列表没有旋转。
示例
- 输入
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- 输出
- 4
- 解释
- 索引 3 处的第一个中间元素是 2，因此右半部分
[2, 5, 8, 11]已排序，其中包含 5。接下来，索引 5 处的中间元素是 8；已排序的左侧部分[5, 8]包含 5，因此得到索引 4。
- 输入
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- 输出
- -1
- 解释
- 65 应该位于 60 和 70 之间，但没有元素存储它。第一个中间值 70 会把 65 定位到已排序的左侧部分
[40, 50, 60, 70]中，范围会在那里不断缩小，直到为空。
- 输入
- nums = [8, 13, 21, 1, 3, 5]target = 13
- 输出
- 1
- 解释
- 第一个中间位置的索引是 2，存放着 21。左侧部分
[8, 13, 21]已排序，13 位于 8 和 21 之间，因此舍弃右侧部分。随后，搜索在索引 1 处找到 13。
进阶
如果 nums 中可能有重复项，就没有算法能保证时间复杂度为 O(log n)。你能用一个经过旋转、由多个 1 和一个被隐藏的 0 组成的列表来证明这一点吗？
提示
逐个打开提示，每个都会多透露一点。
任选一个中间索引，看看它两侧的两部分。旋转后，数组中会有一个位置，值从最大值降到最小值。这个降序位置会同时出现在两部分中吗？
至少有一半始终是有序的，比较
nums[lo]和nums[mid]就能判断是哪一半。对于有序的一半，你可以一步判断target是否位于它的第一个值和最后一个值之间。让
lo和hi始终框住仍可能包含target的部分。每一步，如果已排序一半的值范围包含target，就保留这一半；否则保留另一半。找到target或范围为空时停止。
题解
旋转后的有序列表由两段有序序列组成：[15, 19, 23]，然后是 [2, 5, 8, 11]。将 target 与中间值比较，不再能告诉你它在哪一侧。但无论从哪里切分列表，至少有一半是有序的，只需比较一次，就能判断 target 是否可能在这一半中。
扫描每个元素
思路
检查每个索引，并返回值等于 target 的第一个索引；如果循环结束后仍未找到，则返回 -1。它会读取每个元素，因此对任何列表都适用。它没有利用这两个有序区段：5000 个元素最多需要比较 5000 次，而二分查找只需要 13 次。
算法
- 对于从 0 到
n-1的每个索引i，将nums[i]与target进行比较。 - 如果它们相等，就返回
i。 - 循环结束后，返回
-1。
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1找到旋转点，然后进行二分查找
思路
第二段从最小值开始，将它的索引记为 k。nums[k..n-1] 和 nums[0..k-1] 都是有序的，并且第一段中的每个值都大于第二段中的每个值。知道 k 后，将 target 与 nums[k] 和 nums[n-1] 比较，就能确定目标值所在的段，然后用普通的二分查找完成搜索。
要找到 k，将中间值与 nums[hi] 比较。如果 nums[mid] > nums[hi]，说明 mid 之后某处出现了下降，因此最小值在它右侧。否则，nums[mid..hi] 是递增的，中间没有下降，因此最小值在 mid 处或其左侧。在第一个示例中，中间值依次是 2、19 和 23，因此 k = 3，而 5 位于 nums[3] = 2 和 nums[6] = 11 之间。两次二分查找大约需要 2 log2 n 步。
算法
- 设置
lo = 0和hi = n-1。当lo < hi时，计算mid；如果nums[mid] > nums[hi]，则设置lo = mid + 1，否则设置hi = mid。 - 最终索引
k对应最小值。 - 如果
nums[k] ≤ target ≤ nums[n-1]，就在索引k到n-1的范围内进行二分查找；否则就在索引 0 到k-1的范围内查找。 - 返回找到的索引；如果范围为空，则返回
-1。
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1在已排序的一半中进行一次二分查找
思路
保持二分查找的特性：如果 target 在列表中，它的索引就在 lo 和 hi 之间。整个列表中的值只会下降一次，因此以 mid 为界的两半中，最多只有一半包含下降点，另一半是有序的。如果 nums[lo] ≤ nums[mid]，左半部分有序；否则右半部分有序。
对于有序的一半，检查两端的范围就能判断 target 是否可能在其中，例如左半部分的范围是 nums[lo] ≤ target < nums[mid]。如果可能，就在这一半查找；否则，target 只能在另一半。每一步都会将范围减半：对于 5000 个元素，最多需要 13 步。
算法
- 将
lo = 0和hi = n-1设为初始值。 - 当
lo ≤ hi时，计算mid，如果nums[mid]等于target，就返回它。 - 如果
nums[lo] ≤ nums[mid]，左半部分是有序的：当nums[lo] ≤ target < nums[mid]时，设置hi = mid - 1；否则设置lo = mid + 1。 - 否则，右半部分是有序的：当
nums[mid] < target ≤ nums[hi]时，设置lo = mid + 1；否则设置hi = mid - 1。 - 循环结束后，返回
-1。
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
易错点和边界情况
- 写成
nums[lo] < nums[mid]，而不是≤。只剩两个元素时，mid等于lo，严格比较会把[9, 4]判断为已排序的右半部分：target = 4会返回-1。 - 先比较
target和nums[mid]。在第一个示例中，target = 19，中间值 2 更小，因此搜索会向右移动，从而错过索引 1。 - 只检查已排序半部分的一端。在
[40, 50, 60, 70, 80, 10, 20]中，target = 80时，仅使用target ≥ nums[lo]会让搜索进入[40, 50, 60, 70]。 - 在 Rust 中，当
k = 0（列表未旋转）时，对usize执行k - 1会发生下溢。请使用左闭右开区间。 - 在 Lua 和 R 中，返回的是从 1 开始的位置。请减去 1。
常见问题3
搜索旋转排序数组的时间复杂度是多少？
时间复杂度为 O(log n)，额外空间复杂度为 O(1)。每一步都会保留范围的一半，因此 5000 个元素最多需要 13 步。先找到旋转点也是 O(log n)，所需步骤大约是其两倍。
当数组中包含重复项时，这个算法还能正常工作吗？
不能直接这样写。当 nums[lo]、nums[mid] 和 nums[hi] 相等时，无法证明哪一半是有序的。通常的解决方法是在这种情况下将 lo 向前移动一位，这样可以保证答案正确，但最坏情况下的时间复杂度为 O(n)。
你应该先找到旋转点，还是一次遍历完成搜索？
两者的运行时间都是 O(log n)。先找到最小值，就能把问题拆分成两个普通的二分查找。单次遍历查找只需一个循环，步骤更少，也是大多数面试官所期望的做法。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def search(nums, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
预期输出
4