Algorithmic Design to Undo Rotation of Array An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$.

That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $A_k$.

Devise a $\Theta(\lg(n))$ algorithm to recover $k$ from $A_k$ where $\lg(n) = \log_2(n)$.

To clarify, the algorithm needs to determine what the shift $k$ applied to $A$ was which resulted in $A_k$. Thus, $A_k$ is sufficient enough for the algorithm to work with in order to determine the shift since we know that $A$ consisted of ascending integers.

Any help or insight would be greatly appreciated!
I assume this is a homework question, so I will not solve it for you. I'll just give you some hints.

The problem is basically to find the drop in $A_k$, that is the pair of consecutive elements such that the second one is smaller than the first one. Indeed, these two must be the last and first element of $A$.

Now, if you are given a subinterval of $A_k$, how can you tell whether it contains the drop? Hint: It can be done in $\Theta(1)$.