题目描述
LeetCode 33 — 搜索旋转排序数组 (Medium)
整数数组 nums 原本按升序排列，且所有元素互不相同。数组可能在某个未知的 pivot 位置 k（1 <= k < nums.length）被旋转——旋转后的数组变成 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。
给定旋转后的数组 nums 和一个整数 target，返回 target 在 nums 中的下标，如果不存在则返回 -1。要求时间复杂度 O(log n)。
示例 1：
- 输入：
nums = [4,5,6,7,0,1,2],target = 0 - 输出：
4
示例 2：
- 输入：
nums = [4,5,6,7,0,1,2],target = 3 - 输出：
-1
示例 3：
- 输入：
nums = [1],target = 0 - 输出：
-1
约束：
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums中所有元素互不相同nums是一个可能经过旋转的升序数组
求解思路
题目要求 O(log n)，加上在有序数组中查找，直觉就是二分。但这题的数组被旋转过，并不是全局有序的——比如 [4,5,6,7,0,1,2]，没法直接用经典二分。
直接线性扫描是 O(n)，能过但不符合题目要求的 O(log n)。那二分还有机会吗？
关键观察：对于一个旋转过的有序数组，任取中间位置 mid，至少有一半是严格有序的。以 [4,5,6,7,0,1,2] 为例，mid=3（值为 7），左半边 [4,5,6,7] 是有序的，右半边 [7,0,1,2] 则不是。换成 [5,6,7,0,1,2,3,4]，mid=3（值为 0），左半边 [5,6,7,0] 不是有序的，但右半边 [0,1,2,3,4] 是有序的。这个性质从旋转的定义出发不难理解：旋转点只会切断一次数组的连续性，而 mid 最多和这个切断点相交一次，因此 mid 的两侧不可能同时被切断，总有一侧保持连续。
有了这个性质，二分就可以继续用：每次取 mid，判断哪一半有序，然后判断 target 是否落在有序那一半的范围内。如果在，就去这一边继续搜；如果不在，target 必然在另一侧。这样一来，每一步仍然可以排除一半的数据，维持 O(log n)。
具体判断左半是否有序的条件很简单：nums[left] <= nums[mid]。这里用 <= 而不是 <，是因为当 left 和 mid 重合时（只剩两个元素），左半边仍然算有序。如果左半有序且 nums[left] <= target < nums[mid]，则 target 落在左半区间，收缩右边界；否则 target 在右半，收缩左边界。反过来，左半不是有序的话，右半一定有序，对称地判断 nums[mid] < target <= nums[right] 即可。
解法：二分搜索
#include <vector>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// 左半部分 [left, mid] 有序
if (nums[left] <= nums[mid]) {
// target 在左半有序区间内
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 否则右半部分 [mid, right] 必定有序
else {
// target 在右半有序区间内
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
};
复杂度： 时间 O(log n)；空间 O(1)。
相关题目
- LeetCode 153 — 寻找旋转排序数组中的最小值
- LeetCode 154 — 寻找旋转排序数组中的最小值 II（允许重复元素）
- LeetCode 81 — 搜索旋转排序数组 II（允许重复元素）
- LeetCode 704 — 二分查找（经典二分，本题的基础）