leetcode #33 search in rotated sorted array

wonderful world·2021년 12월 3일
0

leetcode

목록 보기
6/21

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def findpivot(nums):
            #4 5 6 7 0 1 2 3
            l = 0
            r = len(nums)-1
            m = (l+r)//2
            
            while l<r:
                #print(l,m,r)
                v1=nums[m]
                v0=nums[l]
                v2=nums[r]
                
                if v0 < v2:
                    return l
                if v1 < v0:
                    r=m
                else:
                    l=m+1
                m=(l+r)//2
            return l
        def search(nums,l,r,t):
            m = (l+r) // 2
            while l < r:
                print (l,m,r)
                v = nums[m]
                if v == t:
                    return m
                if v < t:
                    l=m+1
                else:
                    r=m
                m=(l+r) // 2
            if nums[l] == t:
                return l
            return -1

        pivot=findpivot(nums)
        #print(pivot)
        if target <= nums[-1]:
            l=pivot
            r=len(nums)-1
        else:
            l=0
            r=pivot-1
          
        i = search(nums,l,r,target)
        
        return i
                    
                
profile
hello wirld

0개의 댓글