# 81. Search in Rotated Sorted Array II

## 刷题内容

• 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());
}
};


apachecn/AiLearning