Question

Let variable A be a zero-index array that is sorted. Now suppose that someone comes along and cyclicly "shifts" the contents of A so that the contents are moved some number of positions, with those at the end being shifted back to the be-ginning. For example, if the array contained the elements 2;6;10;20;30;40 and it were shifted by 3 positions, the resulting array would be 20;30;40;2;6;10 (in general, you will not be given how many positions the array has been shifted).
Design an efficient algorithm that can compute the median element of A. Give good pseudocode and a short explanation. Analy

Answer 1

The language matters on this one, many langauges have built in sort functions that would allow you to re-sort the list with a single step

Answer 2

So, the array is already sorted, and then it is shifted.

To find the median element, we only need to go to the sorted (pre-shifted) middle of the array. Since it is shifted, however, things are complicated slightly. First, we need to find out how many units it has been shifted. This can be done by finding precisely where in the array we see adjacent elements going down instead of up, i.e., A[i] > A[j]. (Let's assume, for simplicity, that each element in the array is unique. We can solve the slightly harder case later, if needed.)

This can be done, inefficiently, by just doing a linear scan through the array, with an expected time complexity of O(n). We can do better, though. So, here's how I'd do it.

Note that if, in the shifted array, A[i] is the smallest value in the array, then A[0] is larger than anything in the range from A[i] to A[len(A)-1]. So, let's simply do a binary search on the array, looking for the following adjacent conditions: A[i] > A[i+1]. How?

Pseudo-code:

find_units_shifted(A, lo, hi)
mid = (hi - lo) / 2

if A[mid] > A[mid+1]
return mid

if A[mid] > A[0]
return find_units_shifted(A, mid+1, hi)
else
return find_units_shifted(A, lo, mid-1)

This will find the index for which A[i] > A[i+1] in log(N) time. Once we have this index, what's next do you think?

Answer 3

Excuse some of the errors in my explanation, especailly at the start. The pseudocode is the most precise explanation.

Also note that I ignore a lot of edge cases, e.g., what if A[mid+1] doesn't exist, i.e., outside the boundary of the array? If you get to this point, where A[mid] is the last element, then return it; clearly, no other point in the array had the condition A[i] > A[i+1], thus it must have been shifted by len(A)-1 units.