【LeetCode】33. Search rotation sort array

1. subject

In fact, this question is very difficult .

2. thought

When you get this question , My first consideration is ：

• Find the rotation boundary of the array , Then we can restore the array （ Get an ordered array ）, Then quickly locate according to the binary search .
  But the problem is ： Whether it is necessary to find the rotation boundary of the array ？ In fact, there is no need . Is there any other way to solve this problem ？

In the traditional two categories , We all use mid The value at the subscript is used as the basis for judgment , But that's true in a completely ordered array , If an array is not completely ordered , Is there any other way to judge ？ For example, in this question , The given condition of the title is ： Arrays are originally ordered , After a rotation operation, it becomes disordered , So when you look up , We can see that in fact [left,mid-1],[mid,right] There must be an ordered array in the . for instance ： In the array [6,7,1,2,3,4,5], We enumerate the number of any subscript , Will find that mid The two intervals divided into satisfy At least one interval is ordered , According to this feature , We can get a complicated version of the dichotomy . And then do analysis in these two sub intervals , The problem is solved .

3. Code

can AC The code for is as follows ：

class Solution:
    #  obtain 
    def search(self, nums: List[int], target: int) -> int:
        left ,right = 0, len(nums)-1
        while(left <= right):
            mid = (left + right) // 2 
            if nums[mid] == target: #  The first comparison here avoids the second comparison 
                return mid
            if left == mid:
                left = mid+1
                continue
            #  At least one end is orderly  
            #  First judge how many numbers there are , Is the left side orderly 
            if nums[left] <= nums[mid-1]:
                if nums[left] <= target and target <=nums[mid-1]: #  In the following interval, find two points 
                    right = mid-1
                else: #  If it's not in this range , Maybe in the other half 
                    left = mid+1
            else : #  Right order 
                if nums[mid] <= target and target <=nums[right]: #  In the following interval, find two points 
                    left = mid+1 
                else: #  If it's not in this range , Is still in the left half 
                    right = mid-1
        return -1

The following code is my first impression idea ,

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        bound_idx = get_bound(nums)
        if bound_idx == 0:
        
        else:

    def get_bound(self,nums):
        idx = 1
        if len(nums) > 1 :
            if nums[idx] > nums[idx-1]: #  The first two numbers are in ascending order 
        else:
            return idx-1 #  Go straight back to 0

        nxt = idx << 1 #  The left one 
        while(idx < len(nums) and nums[idx] < nums[nxt]):
            idx = nxt

        #  Indicates that in the interval  [idx,nxt]  There is a 
        return idx #  Returns the subscript