2
$\begingroup$

I was given a problem concerning a sorted array that is shifted by some "number of spaces", k.

For example, take the sorted array

$1, 2, 3, 4, 5 ,6$

It is shifted 2 spaces, we get:

$5, 6, 1, 2, 3 ,4$

The problem asked "how do you efficiently find a specific value"?

The solution, in this case, I found, is found in the fact that the array is now just split into TWO sorted arrays - we merely find the pivot and binary search on the divided sublists.

My question though, is if there a similarly $\Theta(\log n)$- algorithm to find the actual value $k$? Like - how much the array was actually shifted?

This question, to me, seems much more interesting than the "find a value" question! I'm working at a solution now - what think you, SEMath?

$\endgroup$
4
$\begingroup$

You can do it by bisection. Let's take a longer array, $11,12,13,\dots 29,1,2,3,\dots 10$ If you pick an element $n$, if $n \ge 11$ the break is to the right of $n$ and if $n \le 10$ the break is to the left of $n$.

$\endgroup$

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.