Recursive solution in Python - Very simple implementation


  • 0
    S
    class Solution:
        def search(self, A, target):
            def get(start, end):
              if start > end:
                return -1
              mid = (start+end)/2
              if A[mid] == target: 
                return mid
              elif A[mid] >= A[start]: # First half is sorted
                if target >= A[start] and target < A[mid]:
                  return get(start, mid-1)
                else:
                  return get(mid+1, end)
              elif A[mid] <= A[end]: # Second half is sorted
                if target > A[mid] and target <= A[end]:
                  return get(mid+1, end)
                else:
                  return get(start, mid-1)
            
            return get(0, len(A)-1)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.