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:

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:

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.

3. Code

Here's the recursive code:

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:

Time Complexity $O(\log n)$

Space Complexity $O(1)$