finding an element of in a sorted array thats shifted

Question

Possible Duplicate:
Searching a number in a rotated sorted Array

Say the original list is 1 2 3 4 5 6 7 8 9 10

and u shift it so that it becomes

5 6 7 8 9 10 1 2 3 4

so say i want to check if 7 is in the array. how would i do this efficiently.

Answer 1

Unshift the list (whether physically, or just via lookup logic), then binary search?

Answer 2

Use a variation of binary search to find the point in the array where an element is less than the the prior element; this identifies the shift point. Now break the array in half at that point and do a binary search in whichever half contains the element you're searching for.

Answer 3

Use ternary search. It works similarly to binary search (and also in logarithmic time), but lets you find the element when the sequence is shaped like a wedge (/) or a vee (\/).