原本，整数数组
nums 按升序排列，数组中的值 互不相同 。但
nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。例如，
[0,1,2,4,5,6,7] 下标 3 上向左旋转后变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组
nums 和一个整数 target 。如果
nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。必须设计一个时间复杂度为
O(log n) 的算法解决此问题。示例 1：
示例 2：
示例 3：
解法一：先找到旋转点，再做二分
旋转后的数组虽然整体不再有序，但它仍然保留了一个非常强的结构：由两段各自有序的升序数组拼接而成。
比如：
[4,5,6,7,0,1,2] = [4, 5, 6, 7] + [0, 1, 2]最直观的做法是把问题拆成两步：
- 先找到旋转点，也就是数组里的最小值位置。
- 按旋转点把数组重新切成两个有序区间。接下来只需要判断
target可能在哪个区间，然后在那个区间里做标准二分查找。
我们可以用先用二分查找找旋转点，因为最小值一定在旋转后的第二段开头。
- 如果
nums[mid] > nums[-1]，说明mid还在左侧较大的有序段里，最小值一定在右边。
- 否则，
nums[mid] <= nums[-1]，说明mid已经在右侧较小的有序段里，最小值可能就是mid或在它左边。
复杂度分析
- 时间复杂度是
O(log n)。 - 先用一次二分找到 pivot，
- 再用一次二分查找目标值，
总体仍然是
O(log n)。- 空间复杂度是
O(1)，只使用了常数个指针变量。
解法二：先找到 pivot，再用“虚拟下标”做二分
旋转数组的本质是 一个升序数组被整体平移了。旋转只是改变了下标，不改变值的相对升序关系。
既然如此，我们可以想象把它“转回去”，恢复成原来的升序数组。
在如同 解法一 那样先找到
pivot后，只要用取模映射下标，就可以在虚拟有序数组上做标准二分。还是这个例子：nums = [4, 5, 6, 7, 0, 1, 2]
虚拟数组下标
mid 对应原数组下标：realMid = (mid + pivot) % n这样我们就可以像在普通升序数组里一样做二分，只是每次比较时用
nums[realMid]。复杂度分析
- 时间复杂度是
O(log n)。 - 一次二分找 pivot，
- 一次二分查找 target。
- 空间复杂度是
O(1)。
没有创建额外数组，只是通过取模完成下标映射。
解法三：一次二分 （推荐）
前两个解法都先找 pivot，再查 target。它们很容易理解，但还可以更进一步：不显式找 pivot，而是在每一轮二分里判断哪一半是有序的。
旋转数组虽然整体不是有序的，但任意切一刀，把区间
[left, right] 分成：[left ... mid] 和 [mid ... right]这两半里，至少有一半一定是有序的。
我们要做的事情，是在每一轮二分中安全地丢掉一半搜索空间。
- 如果
nums[left] <= nums[mid]，说明左半边有序。
既然左半边有序，我们就可以通过和
nums[left] 以及 nums[mid] 两个值的比较，判断 target 是否落在这个有序区间里：nums[left] <= target < nums[mid]如果在，那就保留左半边；否则丢掉左半边，去右边找。
- 反过来，说明左半边不是有序的，那么右半边一定有序。
此时通过和
nums[mid] 以及 nums[right] 两个值的比较，判断 target 是否落在这个有序区间里：nums[mid] < target <= nums[right]如果
target 落在右半边的有序区间里，就去右边；否则去左边。这个解法在每一轮先找到有序的一半，就能通过简单的比较判断 target 是否在这一半里，也就可以丢掉另一半搜索空间。
复杂度分析
- 时间复杂度是
O(log n)
每一轮都会丢掉一半搜索区间。
- 空间复杂度是
O(1)
只使用了
left、right、mid 三个指针变量。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-33-搜索旋转排序数组
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 32] 最长有效括号
下一篇
[Leetcode 34] 在排序数组中查找元素的第一个和最后一个位置