# A Shifted Sorted Array - finding the shift

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?

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