Rotated arrays

[dcell59]

In a recent interview, I was asked to consider what was called a "rotated array". This data structure is an array where the data is sorted, but the beginning of the data is not neccessarily the first element of the array. For example, these arrays are equivalent:

{ 1, 2, 3, 4, 5 }
{ 3, 4, 5, 1, 2 }
{ 5, 1, 2, 3, 4 }

The interview questions involved figuring out how to search for an item in this array, given only the array and the size of the array - I was not given the index or value of the lowest data value. When I said I thought that it was bad design to pass around an incomplete data structure like this, I was told that this sometimes happened and that I might need to deal with a case like this.

I was able to come up with a linear search that would also note whether or not the beginning of the sorted list had been encountered, and use that information to reduce the search time.

We then discussed various search algorithms and talked about binary searches. The interviewer insisted that this could be done with a binary search - still without knowing where the lowest value is. Can anyone think of how this might be done?

It does seem like there is a property of such an array that can be applied: When you partition a rotated array, one partition will be sorted and the other will be a rotated array. Once you have split the array into two pieces, you can determine whether each piece is sorted. If the item being searched for is in the sorted piece, you can do a binary search. If not, you can recurse on the other piece. Does this seem like a valid method?

[wildfrog]

AFAIK you just need to 'finetune' the compare algorithm, then leave the binary search algorithm as-is.


int f = // first value in array
bool less(int x, int y) // x = is current value, y is what we're searching for
{
if (x < y && y < f)
{
// elements must be ordered [F...W...X...Y...]
// we need to increase the index
return true; }

if (x >= f && y < f)
{
// elements must be ordered [F...X...W...Y...]
// we need to increase the index
return true;
}

if (x < y && x >= f)
{
// elements must be ordered [F...X...Y...W...]
// we need to increase the index
return true;
}

// for all other cases :
// [F...W...Y...X...]
// [F...Y...X...W...]
// [F...Y...W...X...]
// we need to decrease the index
return false;
}

- petter

[dcell59]

I'll have to give that a try. I'm not sure how it would work for very large arrays. I still think the whole problem is a little impractical, since any real system designed to use rotated arrays will also maintain the base index, but it's a fun one to solve.

My idea was a little more "manual". You do it by having 2 search algorithms: a regular binary search and a "rotated" binary search. The "rotated" binary search simply splits the array into 2 parts, checks the center point, and then calls the appropriate search on each part. The algorithm is still O(logN), but it's just more likely to be closer to logN.

[wildfrog]

I'm sure your solution would work, but would it still be regarded as a binary search?

- petter

[dcell59]

Good question. In the purest sense, a binary search simply means dividing the set into two parts, determining which part the item may be in, and then doing a binary search on that part. You stop when your set only has one element.

In a binary search of a sorted array, the second step is simple. You know both parts are sorted, so you can determine which part the item may be in by doing simple comparisons. You get the special added benefit of finding out if the item is "between" the two parts, and therefore isn't in the set.

In the rotated array search, the only difference is that you can only be guaranteed that one of the parts is sorted. As a result, you can know that the item is inside of that part, but you can't know that it is not inside of a non-sorted part.

In fact, the algorithm could be restated as:

if size of set is 1 and set[0] == item, return info on set[0]
divide the set into parts A and B
if A is sorted and the item is in the A's range, return Search(A)
if B is sorted and the item is in the B's range, return Search(B)
if A is not sorted, return Search(A)
if B is not sorted, return Search(B)
return "not found"

This works whether the array is sorted or rotated. In the case of a sorted array, A and B are never "not sorted", so you are doing two comparisons are aren't neccessary. Of course, once you know this, you could simply pass down a flag saying so.

So, in my opinion, it's a binary search. It's also a more interesting interview question than I originally considered it.