Search in Rotated Sorted Array (Leetcode 33)
Problem Link: https://leetcode.com/problems/search-in-rotated-sorted-array/
class Solution:
def search(self, nums: List[int], target: int) -> int:
def modifiedbsearch(nums,i,j):
mid=(i+j)//2
while(i<=j):
if(nums[i]<=nums[j]):
return i
if(nums[mid]>=nums[i]):
return modifiedbsearch(nums,mid+1,j)
else:
return modifiedbsearch(nums,i,mid)
def bsearch(nums,i,j,target):
mid=(i+j)//2
while(i<=j):
if(nums[mid]==target):
return mid
elif(nums[mid]<target):
return bsearch(nums,mid+1,j,target)
else:
return bsearch(nums,i,mid-1,target)
return -1
n=len(nums)
# Find the shortest element
idx=modifiedbsearch(nums,0,n-1)
# Do Bsearch on left part
a=bsearch(nums,0,idx-1,target)
# Do Bsearch on right part
b=bsearch(nums,idx,n-1,target)
if(a!=-1):
return a
elif(b!=-1):
return b
else:
return -1
Last updated