1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – turing Oct 8 '18 at 18:00
  • $\begingroup$ 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. $\endgroup$ – kne Oct 8 '18 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.