假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 0,0,1,2,2,5,6 可能变为 2,5,6,0,0,1,2 )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
这是 LeetCode 33 搜索旋转排序数组 的延伸题目,本题中的 nums 可能包含重复元素。
类似题目:程序员面试金典 - 面试题 10.03. 搜索旋转数组(二分查找)
if(nums[left] == nums[mid] && nums[mid] == nums[right])
{//在leetcode33基础上增加 这种条件
left++, right--;
continue;
}
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1, mid;
while(left <= right)
{
mid = left+((right-left)>>1);
if(nums[mid] == target)
return true;
if(nums[left] == nums[mid] && nums[mid] == nums[right])
{//在leetcode33基础上增加 这种条件
left++, right--;
continue;
}
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 false;
}
};