 You're given a rotated and sorted array `arr`. You're also given the number `target` to look for. Returrn the index of the target. If the target is not in the array, return None. The values in the array are unique. Example: Explanation: The target is located at index 3. 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

Search a Rotated Sorted Array

-----problem-----

You're given a rotated and sorted array `arr`. You're also given the number `target` to look for. Returrn the index of the target. If the target is not in the array, return None.

 The values in the array are unique. 


    \b{Example:} 
    
    \image{0,50}
    $$
    
    \begin{align*}
    & \texttt{arr = [9, 12, 14, 1, 2, 4, 5, 7, 8]} \\
    & \texttt{target = 1} \\[8bp]
    & \texttt{=> returns 3}
    
    \end{align*}
    $$
\b{Explanation:} The target is located at index 3.

-----solution-----


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)
``


\s2

The first thing to realize is that the Array is broken into 2 parts that are sorted, like this:
\image{lr,100}

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


\image{c1,160}



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:


\image{c2, 160}


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.
}
``

\s3


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
``

\s4


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

\spoiler{

```
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)
```
}


\tc $O(\log n)$

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

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

\answer
\tc $O(\log n)$

\sc $O(1)$





Recursion

Search a Rotated Sorted Array