Search in a sorted array of ints which rolls over

Question

Is there a easy way to search in an array like this? Some examples below :

5 6 7 8 19 45 21 32 40  // Rolled over at 7 th element
15 22 32 45 121 341 40  // Rolled over at 7 th element
1 22 32 45 121 341 400  // Rolled over at 0 th element

Answer 1

If you're going to do many searches, you could do one pre-processing pass, using linear search, to get the indices of all the rollover places, then do binary search within each section.

But if you're going to search just once I think you have to do linear search. So either way there's a linear search involved.

If you go with the "find rollover first" technique, and you know there's only one rollover point, you can at least bail out of that linear search as soon as you find the point.

Answer 2

Any algorithm to find "rollover" point would have at least O(n) complexity in worst case.

Imagine, you have sorted array and checked less than n of its elements. For example, if in array 1 2 3 4 5 6 7 8 9 10 you didn't check element 4, I can replace it with 100 and create "rollover" (1 2 3 100 5 6 7 8 9 10). Your algorithm won't know, since it never read this element.

Thus, your only option is to go through all elements until you find rollover.

Thanks to Eyal Schneider for a useful comment.

BTW, am I the only one here who doesn't understand etymology of the word "rollover"?

Answer 3

Think of your array as a mathematical function, what you want is the local maxima of your function. Although I don't have enough knowledge to explain, you might want to do some research about Hill Climbing. Using some heuristics, you might be able to find your local maxima more efficiently.

Answer 4

this should help http://geeksforgeeks.org/?p=1068