【leetcode】81. Search rotation sort array II

subject ：

81.  Search rotation sort array  II
 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
-104 <= nums[i] <= 104
 Topic data assurance  nums  Rotated on a previously unknown subscript 
-104 <= target <= 104

Dichotomy ：

class Solution {
    
    public boolean search(int[] nums, int target) {
    
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while(l <= r){
    
            int mid = (l + r) / 2;
            if(nums[mid] == target) return true;
            //  Order on the right 
            else if(nums[mid] < nums[r]){
    
                if(target > nums[mid] && target <= nums[r]){
    
                    l = mid + 1;
                }
                else{
    
                    r = mid - 1;
                }
            }   
            //  Order on the left 
            else if(nums[mid] > nums[r]){
    
                if(target < nums[mid] && target >= nums[l]) {
    
                    r = mid - 1;
                }
                else{
    
                    l = mid + 1;
                }
            }
            //  Right side weight removal 
            else r--;
        }
         return false;
    }
}

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