Skip to content

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


回到顶部