题目描述
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转
(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。
请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
样例
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
输入:nums = [1], target = 0
输出:-1
算法1
(二分) $O(logn)$
根据LeetCode 153. 153. 寻找旋转排序数组中的最小值【二分】把数组分为前半段和后半段,然后根据target <= nums.back()
确定是在前半段还是后半段,根据有序数组查找一个数二分查找即可。
时间复杂度 $O(logn)$
C++ 代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
if(target <= nums.back()) r = nums.size() - 1;
else l = 0, r --; // 若只有一个元素,这里r--可能变为-1,溢出,下面用l表示
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[l] != target) return -1;
return l;
}
};