33搜索旋转排序数组

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        
        def search_II(left,right):
            while left<=right:
                mid = (left+right)>>1
                if nums[mid]==target:
                    return mid
                elif nums[mid] < target:
                    return search_II(mid+1,right)
                else:
                    return search_II(left,right-1)
            return -1
        
        def find_rotation_point(nums):
            # return nums.index(min(nums))
            left = 0
            right = len(nums)-1
            while left<right:
                mid = (left+right)>>1
                if nums[mid]<nums[right]: # 一定不在右侧
                    right = mid
                else:
                    left = mid+1
            return left 
        
        rotation_point = find_rotation_point(nums)
        print(rotation_point)
        if target >= nums[rotation_point] and target <= nums[right]:
            result = search_II(rotation_point,right)
        else:
            result = search_II(left,rotation_point-1)
        # result = search_II(left,rotation_point-1) if search_II(left,rotation_point-1)!=-1 else search_II(rotation_point,right)
        return result