[LeetCode][python3]Day19. Search in Rotated Sorted Array (30-Day LeetCoding Challenge)

class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
pivot=int(len(nums)/2)
l=0
r=len(nums)-1
if target==nums[l]:
return 0
elif target==nums[r]:
return r
else:
return self.binsearch(nums,l,r,target)

def binsearch(self,nums,l,r,target):
if l+1>=r:
return -1
else:
pivot=int((r+l+1)/2)
#print(pivot,nums[l],nums[r],nums[pivot])
if nums[pivot]==target:
return pivot
elif nums[r]>nums[l]:
if target<nums[pivot]:
return self.binsearch(nums,l,pivot,target)
else:
return self.binsearch(nums,pivot,r,target)
else:
if nums[pivot]>nums[l]:
if nums[pivot]>target>nums[l]:
return self.binsearch(nums,l,pivot,target)
else:
return self.binsearch(nums,pivot,r,target)
elif nums[pivot]<nums[l]:
if nums[pivot]<target<nums[r]:
return self.binsearch(nums,pivot,r,target)
else:
return self.binsearch(nums,l,pivot,target)
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
elif nums[m] >= nums[l]:
if target >= nums[l] and target < nums[m]:
r = m - 1
else:
l = m + 1
else:
if target > nums[m] and target <= nums[r]:
l = m + 1
else:
r = m - 1
return -1

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ruka

Ruka

HI I’m Ruka. Now a SWE in Taiwan. Contact via email: nayzi9999@gmail.com