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