Leetcode（81）—— Search rotation sort array II

subject

It is known that there is an array of integers in non descending order nums , The values in the array don't have to be different from each other .

Before passing it to a function ,nums In some unknown subscript k（$0<=k<nums.length$） On the rotate , Make array [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（ Subscript from 0 Start Count ）. for example , [0,1,2,4,4,4,5,6,6,7] In subscript 5 It may turn into [4,5,6,6,7,0,1,2,4,4] .

Here you are. After rotation Array of nums And an integer target , Please write a function to determine whether the given target value exists in the array . If nums There is a target value in target , Then return to true , Otherwise return to false .

You must minimize the whole procedure .

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

Tips ：

$1$ <= nums.length <= $5000$
$-10^4$ <= nums[i] <= $10^4$
Topic data assurance $nums$ Rotated on a previously unknown subscript
$-10^4$ <= target <= $10^4$

Advanced ：

• This is a Search rotation sort array The extended topic of , In this question $nums$ It may contain repeating elements .
• Does this affect the time complexity of the program ？ What kind of impact will it have , Why? ？

Answer key

Method 1 ： Two points search

Ideas

​​   But and 33. Search rotation sort array The difference is , The element of this question is not unique . This means that we cannot directly base on nums[0]nums[0] The size of the relationship , Divide the array into two segments , I.e. unable to pass 「 Two points 」 To find the rotation point . because 「 Two points 」 The essence of is dualism , Not monotonicity . As long as a paragraph satisfies a certain property , Another paragraph does not satisfy a certain property , You can use it 「 Two points 」.

​​   Even if the array is rotated , We can still take advantage of the incremental nature of this array , Use binary search . For the current midpoint , If it points to a value less than or equal to the right end , Then it shows that the right interval is well ordered ; conversely , Then it shows that the left interval is in good order . If the target value is within the ordered interval , We can continue the binary search for this interval ; conversely , Let's continue the binary search for the other half of the interval .
​​   Be careful , Because there are duplicate numbers in the array , If the middle and left numbers are the same , We can't be sure that the left intervals are all the same , Or is the right interval exactly the same . under these circumstances , We can simply move the left endpoint one bit to the right , Then continue the binary search .

​​   for example $\text{nums}=[3,1,2,3,3,3,3]$,$\text{target}=2$, The interval cannot be judged at the first dichotomy $[0,3]$ And interval $[4,6]$ Which is orderly .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    bool search(vector<int> &nums, int target) {
    
        int n = nums.size();
        if (n == 0) return false;
        else if (n == 1) return nums[0] == target;
        int l = 0, r = n - 1, mid;
        while (l <= r) {
    
            mid = (l + r) / 2;
            if (nums[mid] == target) return true;
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
    
            	//  Remove the repeating elements , Ensure the duality 
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
    	//  The left interval is in order 
                if (nums[l] <= target && target < nums[mid]) 	//  Judge  target  Is it in the left section 
                    r = mid - 1;
                else l = mid + 1;
            } else {
    	//  The right interval is in order 
                if (nums[mid] < target && target <= nums[n - 1])	//  Judge  target  Is it in the right section 
                    l = mid + 1;
                else r = mid - 1;
            }
        }
        return false;
    }
};

Complexity analysis

Time complexity ：$O(\log n)$. In the worst case, the array elements are equal and not $\text{target}$, We need to visit all locations to get results . The time complexity is $O(n)$, among $n$ It's an array $\text{nums}$ The length of .
Spatial complexity ：$O(1)$