Recursion

Min in a Rotated Sorted Array

Given a rotated sorted array arr, return the minimum value in the array.

Every element in the array is a unique integer.

Example:

\notag \begin{align*} &\texttt{arr = [9, 12, 14, 1, 4, 5, 7, 8]}\\ &\texttt{=> returns 1} \end{align*}

Explanation: The element 1 is the minimum value in the array.

First Few Test Cases:

smallestElement([1, 2, 3, 4, 5, 6, 7])
# 1

smallestElement([6, 7, 1, 2, 3, 4, 5])
# 1

smallestElement([4, 5, 6, 7, 1, 2, 3])
# 1

We want to take advantage of the fact that the Array is sorted, and do a Binary Search.

search(i, j)

1. Recursion

The first thing to realize is the array has 2 parts. We'll call them "left" and "right":

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

In this case, our search should continue towards the left side of the array since that's where the smallest value "1" is. We can do this by searching between i and mid. *

In general, whenever we find ourselves in the "right" part of the array, we want to continue searching towards the left.

The other case is if mid is in the "left" part of the array. In this case, we should search towards the right:

Here's the recursion, putting these two cases together:

search(i, j) = (
    mid = (i + j) // 2

    if "mid is in right part":
        return search(i, mid)

    if "mid is in left part":
        return search(mid+1, j)
)

How do we figure out if mid is in the "left" or "right" part of the array?

If mid is in the right part, then we'll have arr[mid] <= arr[j]:

If mid is in the left part, then we'll have arr[mid] > arr[j]:

Here's the recursion, filling this in:

# recursion
mid = (i + j) // 2
if arr[mid] <= arr[j]:
    return search(i, mid)
else:
    return search(mid+1, j)

It's important to confirm to yourself that these conditions work even in small cases like searching 3, 2, or 1 element, and searching in an unrotated array.

2. Base case

The recursion should keep going until the search interval has narrowed on one element.

if i == j:
    return arr[i]

3. Code

Here's the full code, combining the recursion and the base case:

def smallestElement(arr):
    def search(i, j):
        # base case
        if i == j:
            return arr[i]

        # recursion
        mid = (i + j) // 2
        if arr[mid] <= arr[j]: return search(i, mid)
        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 the above code iterative, like this:

def smallestElement(arr):
    
    i = 0
    j = len(arr) - 1

    while True:
        # base case
        if i == j:
            return arr[i]

        # recursion
        mid = (i + j) // 2
        if arr[mid] <= arr[j]: j = mid
        else:                  i = mid+1

Time Complexity $O(\log n)$

Space Complexity $O(1)$

Here's an alternative solution that uses hijacking. It's slightly more efficient because it uses j = mid-1, eliminating elements faster. But it's a little harder to work through all the edge cases.

Open SpoilerClose Spoiler

Here's how you write this code with i = mid+1 and j = mid-1.

1. Recursion

search(i, j) = (
    mid = (i + j) // 2

    if "mid is in right part":
        search(i, mid-1)

    if "mid is in left part":
        search(mid+1, j)
)

As this recursion runs, we want to keep track of the minimum element that we've seen. The easiest way to do this is to add a global variable that keeps track of this. You need to realize that the minimum element is the leftmost element in the right part of the array.

The binary search always gets closer to this value, so whenever you're in the right part of the array, you can just update the global variable, and at the end it will be the correct value.

search(i, j) = (
    mid = (i + j) // 2

    if "mid is in right part":
        seen = arr[mid] # <-- hijack
        search(i, mid-1)

    if "mid is in left part":
        search(mid+1, j)
)

To check if mid is in the right or left part of the array, we can't just use arr[mid] <= arr[j] like we did before. Our new recursion here might eliminate the minimum element from the search bounds, and if that happens, this condition will give True regardless of whether we're in the left or right part of the array.

To fix this, you can use the comparison arr[mid] <= arr[-1] instead. This works because it compares the middle element with the global very last element, so even if you eliminate the last element from your search bounds it's still valid. This condition is pretty difficult to come up with, considering something like arr[0] <= arr[mid] doesn't work due to the fact that mid gets rounded down. To be confident in your answer, you need to make sure it works on edge cases like searches of size 3, 2, and 1, and even unrotated searches.

2. Base case

When the search has eliminated all the elements, it should stop.

if j == i-1:
    return

3. Code

We can code this up by combining the recursion and the base case. Here's the recursive code:

def smallestElement(arr):
    minSeen = None

    def search(i, j):
        # base case
        if j == i-1:
            return

        # recursion
        mid = (i + j) // 2
        if arr[mid] <= arr[-1]:
            nonlocal minSeen
            minSeen = arr[mid] # <-- hijack
            search(i, mid-1)
        else:
            search(mid+1, j)

    # search the array, computing `minSeen`
    search(0, len(arr)-1)
    return minSeen

Time Complexity $O(\log n)$

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

Here's the iterative version:

def smallestElement(arr):
    
    minSeen = None
    i = 0
    j = len(arr)-1

    while True:
        # base case
        if j == i-1:
            return minSeen

        # recursion
        mid = (i + j) // 2
        if arr[mid] <= arr[-1]:
            minSeen = arr[mid]
            j = mid - 1
        else:
            i = mid + 1

Mark as Completed:

Submits:

smallestElement

Test your code to get an output here!

smallestElement(

)

Test your code to get an output here!