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