【每日一题】33. Search in Rotated Sorted Array
【每日一题】33. Search in Rotated Sorted Array
题目描述
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
题解
暴力循环
首先想到的解法是暴力循环O(N)，不管数组是否有序，直接一次遍历，判断数组中是否有target存在。
虽然，题目中限制了时间复杂度要求，但是O(N)也能通过测试！
class Solution {
public:
int search(vector<int>& nums, int target) {
int idx = -1;
for (int i=0; i< nums.size(); i++){
if (nums[i] == target){
idx = i;
break;
}
}
return idx;
}
};
二分查找
下面看题目要求的结果O(logn)。O(logn)+有序数组->二分查找。题目给定也是一个有序数组经过一次旋转，所以，为了使用二分查找，我们需要在给定的数组中找到有序的片段，然后再利用二分查找法。
步骤：
- 考虑Corner case：空数组，长度为1的数组；
- 其他情况，设定左右边界；
- 如果mid == target，直接退出，返回mid
- 如果nums[left] <= nums[mid],说明left，mid子数组为有序数组，然后我们再来确定，target是否在这个子数组中：
- nums[left] <= target && target < nums[mid]: 在，变换左边界
- 否则，变换右边界
- 如果nums[left] > nums[mid]，说明，mid,right 为有序子数组，然后我们确定，target是否在这个子数组中：
- nums[mid] < targe && target <= nums[right]:在，变换左边界
- 不在，变换右边界
要注意边界调节，left，right不同的初始值，while里的判断条件也不相同，明确是否取等号，此时的left，right如何变换
class Solution {
public:
int search(vector<int>& nums, int target) {
int size = (int)nums.size();
if (size == 0) return -1;
if (size == 1) return nums[0] == target ? 0 : -1;
int idx = -1, left = 0, right = size - 1;
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
idx = mid;
break;
}
if(nums[left] <= nums[mid]){
if (nums[left] <= target && target< nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return idx;
}
};