33. 搜索旋转排序数组
一句话套路先判断哪一半有序,再决定往哪收缩
题目描述
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 向左旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -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-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
思路
时间
O(log n)空间
O(1)核心判断
mid 把数组分成两半,「至少有一半是有序的」。
- · nums[lo] <= nums[mid] -> 左半有序:target 落在 [nums[lo], nums[mid]) 就去左边,否则右边。
· 否则右半有序
target 落在 (nums[mid], nums[hi]] 就去右边,否则左边。
用 nums[lo] <= nums[mid] 而不是 < ,是为了处理 lo == mid(区间长度 2)。
陷阱
本题元素互不相同;若有重复就退化成 Q81,需要 nums[lo]==nums[mid] 时 lo++ 慢慢缩。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0033 {
class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 有序
if (nums[lo] <= target && target < nums[mid])
hi = mid - 1;
else
lo = mid + 1;
} else { // 右半 [mid, hi] 有序
if (nums[mid] < target && target <= nums[hi])
lo = mid + 1;
else
hi = mid - 1;
}
}
return -1;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0033::Solution s;
vector<int> a{4, 5, 6, 7, 0, 1, 2};
CHECK_EQ(s.search(a, 0), 4);
CHECK_EQ(s.search(a, 4), 0);
CHECK_EQ(s.search(a, 3), -1);
CHECK_EQ(s.search(a, 2), 6); // 最小值在末尾附近
CHECK_EQ(s.search(a, 7), 3); // 最大值
vector<int> b{1};
CHECK_EQ(s.search(b, 0), -1);
vector<int> c{3, 1};
CHECK_EQ(s.search(c, 1), 1); // 两元素旋转,考验 lo==mid
CHECK_EQ(s.search(c, 3), 0);
vector<int> d{1, 2, 3, 4, 5}; // 没旋转
CHECK_EQ(s.search(d, 5), 4);