LeetCode 81. 搜索旋转排序数组 II-爱代码爱编程
81. 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:
- 这是 搜索旋转排序数组 的延伸题目,本题中的 nums 可能包含重复元素。
- 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
题解
本题是需要使用二分查找,怎么分是关键,举个例子:
- 第一类
10111和 11101这种。此种情况下nums[start] == nums[mid]
,分不清到底是前面有序还是后面有序,此时 start++ 即可。相当于去掉一个重复的干扰项。 - 第二类
2 3 4 5 6 7 1 这种,也就是nums[start] < nums[mid]
。此例子中就是 2 < 5;
这种情况下,前半部分有序。因此如果nums[start] <=target<nums[mid]
,则在前半部分找,否则去后半部分找。 - 第三类
6 7 1 2 3 4 5 这种,也就是nums[start] > nums[mid]
。此例子中就是 6 > 2;
这种情况下,后半部分有序。因此如果nums[mid] <target<=nums[end]
。则在后半部分找,否则去前半部分找。
代码
class Solution {
public:
bool search(vector<int>& nums, int target) {
int start=0,end=nums.size()-1;
while(start<=end)
{
int mid=(end+start)/2;
if(nums[mid]==target)
return true;
if(nums[mid]==nums[start])
{
start++;
}
// 右边已经排好序
else if(nums[mid] > nums[start])
{
if(target <nums[mid] && target >= nums[start])
end = mid - 1;
else
start=mid+1;
}
else // 左边已经排好序
{
if(target>nums[mid] && target <= nums[end])
start=mid+1;
else
end=mid-1;
}
}
return false;
}
};