To solve this problem, we should try and use some kind of Binary Search since the array is pretty much sorted. We'll create a function that searches for the target, between index i and j (inclusive of both).

search(i, j)

1. Recursion

The first thing to realize is that the Array is broken into 2 parts that are sorted, like this:

It's hard to know where to start, so let's consider some random example to try and make progress:

How should we do a binary search here, where mid is in the right part of the array? The thing to realize is that since mid is in the right part of the array, all the numbers to the right of mid will be in sorted order. This means we can check if the target is to the right of mid by checking if its value is between arr[mid] and arr[j].

Here's the recursion:

# recursion when `mid` is in the "right" part of the array
search(i, j) = (
    mid = (i + j) // 2
    
    if target == arr[mid]:
        return mid

    if arr[mid] <= target <= arr[j]: 
        return search(mid+1, j) # go right
    else:
        return search(i, mid-1) # go left
)

This recursion only holds whenever mid is in the "right" side of the array, but we can go through a similar process to find the recursion when mid is in the left part of the array. Here's a visual of this:

Here's the recursion for this second case:

# recursion when `mid` is in the "left" part of the array
search(i,j) = (
    mid = (i + j) // 2
    
    if target == arr[mid]:
        return mid

    if arr[i] <= target <= arr[mid]:
        return search(i, mid-1) # go left
    else:
        return search(mid+1, j) # go right
)

To get the full recursion, we can combine these 2 cases. We're in the "right" side of the array if arr[mid] <= arr[j]. Otherwise, we're in the "left" side of the array. Here's the code for the recursion:

search(i,j) = {
    if arr[mid] <= arr[j]:
        # Run the code written for the "right" case.
    else:
        # Run the code written for the "left" case.
}

2. Base case

The search is done when there are no more elements left in the search. This happens when j is to the left of i.

if j == i-1: 
    return None

3. Code

To code this up, you combine the recursion and base case. Here's the code:

def rotatedSearch(arr, target):
    def search(i, j):
        # base case
        if j == i-1:
            return None
        
        mid = (i + j) // 2
            
        if target == arr[mid]:
            return mid

        # mid is in "right" part
        if arr[mid] <= arr[j]:
            if arr[mid] <= target <= arr[j]:
                return search(mid+1, j)
            else:
                return search(i, mid-1)
        
        # mid is in "left" part
        else:
            if arr[i] <= target <= arr[mid]:
                return search(i, mid-1)
            else:
                return search(mid+1, j)
            

    return search(0, len(arr)-1)

Time Complexity $O(\log n)$

Space Complexity $O(\log n)$ for the Call Stack.

You can make this recursive function iterative. Here's the code:

def rotatedSearch(arr, target):
    
    i = 0
    j = len(arr) - 1

    while True:
        # base case
        if j == i-1:
            return None
        
        # recursion
        mid = (i + j) // 2
        if target == arr[mid]: return mid
        
        if arr[mid] <= arr[j]: # mid is in "right" part
            if arr[mid] <= target <= arr[j]: i = mid+1
            else:                            j = mid-1
        
        else: # mid is in "left" part
            if arr[i] <= target <= arr[mid]: j = mid-1
            else:                            i = mid+1
            

    return search(0, len(arr)-1)

Time Complexity $O(\log n)$

Space Complexity $O(1)$