81. Search in Rotated Sorted Array II
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/search-in-rotated-sorted-array-ii/submissions/
内容描述
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
˼· **- ʱ¼ä¸´ÔÓ¶È: O(lgN)*- ¿Õ¼ä¸´ÔÓ¶È: O(1)***
·×ªÊý×éÒ»¿ªÊ¼Ïëµ½µÄ¾ÍÊÇÓöþ·Ö·¨£¬ÊµÏÖÆðÀ´Ò²²»ÄÑ£¬¹Ø¼üÊÇÅÐ¶Ï l = mid »¹ÊÇ j = mid£¬²»¹ýÕâÌ⻹Ҫµ¥¶À¿¼ÂÇһϵ±nums[mid] == nums[l] µÄÇé¿ö£¬µ±nums[l] == nums[mid]ʱ£¬·Ö±ð²éÕÒ[l,mid]ºÍ[mid,r]Çø¼äÄÚÊÇ·ñ´æÔÚtarget
class Solution {
public:
bool searchInternal( const vector<int>& Nums, const int Target, int Left, int Right )
{
if ( Right <= Left )
return false;
while ( Left < Right - 1 )
{
int Middle = (Left + Right) / 2;
if ( Nums[Left] == Nums[Middle] )
{
return searchInternal( Nums, Target, Left, Middle )
|| searchInternal( Nums, Target, Middle, Right );
}
if ( Target < Nums[Middle] )
{
if ( Nums[Left] < Nums[Middle] && Nums[Left] > Target )
{
Left = Middle;
}
else
{
Right = Middle;
}
}
else if ( Target > Nums[Middle] )
{
if ( Nums[Left] > Nums[Middle] && Nums[Left] <= Target )
{
Right = Middle;
}
else
{
Left = Middle;
}
}
else
{
return true;
}
}
return Nums[Left] == Target;
}
bool search(vector<int>& nums, int target) {
return searchInternal(nums,target,0,nums.size());
}
};
