Leetcode 33. Search rotation sort array

difficulty ： secondary
frequency ：124

** subject ：** An array of integers nums In ascending order , The values in the array 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,5,6,7] In subscript 3 It may turn into [4,5,6,7,0,1,2] .

Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to -1 .

Their thinking ： Orderly ？ Partial order ？==> Dichotomy search

• See which parts are ordered and target In this section , This part uses the binary search method
• details stay int In the array ,length Attribute , And in the String in ,length Is the method
• It is divided into the left side , Order on the right ;
• The order on the left is divided into The value is on the left , The value is not on the left
• The order on the right is divided into Value on right , The value is no longer on the right

class Solution {
    
    public int search(int[] nums, int target) {
    
        int len=nums.length;
        if(len==0) return -1;
        if(len==1) {
    
            if(target==nums[0]){
    
                return 0;
            }
        }
        int l=0;
        int r=len-1;
        // Because the parts are orderly , To the end , There will always be order 
        // Split the array in two , One of them must be orderly , Another possibility is order , It can also be partially ordered .
        // At this time, the ordered part is searched by dichotomy . The disordered part is divided into two parts , One of them must be orderly , Another may be orderly , Possible disorder .
        while(l<=r){
    
            int mid=(l+r)/2;
            if(nums[mid]==target){
    
                return mid;
            }
            // Order on the left 
            if(nums[l]<=nums[mid]){
    
                // The left is ordered and the value is on the left 
                if(nums[l]<=target &&target<nums[mid]){
    
                    r=mid-1;
                }
                // Order on the left   but   Value on right 
                else{
    
                    l=mid+1;
                }
            }
            //  Order on the right  
            else{
    
                    // The right is ordered and the value is on the right 
                    if(nums[mid]<target&&target<=nums[r]){
    
                        l=mid+1;
                    }
                    // Order on the right   But the value is on the left 
                    else{
    
                        r=mid-1;
                    }
                }
        }
        return -1;
    }
}