Recursion

Max Value Less Than

Given a sorted array arr and an integer high, return the largest element in the array with a value less than high.

First Few Test Cases:

maxValueLessThan([1, 2, 3], 5)
# 3

maxValueLessThan([1, 2, 3], 3)
# 2

maxValueLessThan([1, 2, 3], 1)
# None

1. Recursion

To solve this problem, you should use a Binary Search since the array is sorted. To do a binary search, you should look at the middle value in the array, and either search to the left of it, or search to the right of it.

If the middle value is less than high, you want to find a larger value. This means you should continue searching towards the right.

If the middle value is less than high, you want to find a smaller value. This means you should continue searching towards the left.

Here's the recursion, combining these two cases:

search(i, j) = (
    mid = (i + j) // 2
    if arr[mid] < high:
        search(mid+1, j)
    else:
        search(i, mid-1)
)

The recursion always moves towards the high value. This means the solution to the problem is the most recent value that we see that's less than high. Here's how you keep track of this:

largest = None

search(i, j) = (
    mid = (i + j) // 2
    if arr[mid] < high:

        # update most recent value less than `high`
        largest = arr[mid]

        search(mid+1, j)
    else:
        search(i, mid-1)
)

2. Base case

The easiest way to code up a stopping point for a binary search is when the search is empty, or when j is to the left of i.

if j == i-1:
    return

3. Code

Here's the recursive code:

def maxValueLessThan(arr, high):

    largest = None

    def search(i, j):
        # base case
        if j == i-1:
            return
        
        # recursion
        mid = (i + j) // 2
        if arr[mid] < high:

            nonlocal largest
            largest = arr[mid]

            search(mid+1, j)
        else:
            search(i, mid-1)
    

    # calls search on the array, computing `largest`
    search(0, len(arr)-1)
    return largest

Time Complexity $O(\log n)$

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

We can easily convert this to iterative code to get rid of the Call Stack:

def maxValueLessThan(arr, high):

    biggest = None

    i = 0
    j = len(arr) - 1

    while True:
        # base case
        if j == i-1:
            return biggest
        
        # recursion
        mid = (i + j) // 2
        if arr[mid] < high:
            biggest = arr[mid]
            i = mid+1
        else:
            j = mid-1

Time Complexity $O(\log n)$

Space Complexity $O(1)$

Mark as Completed:

Submits:

maxValueLessThan

Test your code to get an output here!

maxValueLessThan(

)

Test your code to get an output here!