# 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!

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)$$.
• Thank you for the hints, I did not ask for this to be solved for me. I understand that we are looking for the drop in $A_k$, but this will take worst-case $n - 1$ comparisons of $A_k$ or $O(n)$. I need a runtime of $\Theta(lg(n))$. By subsequence of $A_k$, I assume you mean a subset of size $i < n$ of $A_k$? If so, the drop is still detected by doing worst case $i - 1$ comparisons so I am confused as to how $\Theta(1)$ can be achieved. – turing Oct 8 '18 at 18:00
• I now replaced subsequence by subinterval to make it clear that there are no gaps. A subinterval is given by the indices of its two endpoints. And $\Theta(1)$ is already a hint: It implies that you can make only a fixed number of queries into the subinterval. – kne Oct 8 '18 at 19:20