Solution: Recursion

Task

Suppose we’re given a sorted array of $n$ distinct numbers that has been rotated $k$ steps, for some unknown integer $k$ between $1$ and $n$. That is, we are given an array $A[1 .. n]$, such that some prefix $A[1 .. k]$ is sorted in increasing order, the corresponding sux $A[k + 1 .. n]$ is sorted in increasing order, and $A[n] < A[1]$. For example, we might be given the following element array (where $k = 10$): $9 \ 13 \ 16 \ 18 \ 19 \ 23 \ 28 \ 31 \ 37 \ 42 \ 1 \ 3 \ 4 \ 5$ ...