2

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.

Community
  • 1
  • 1
hao
  • 71
  • 3
  • Question: Do you have the control of the shifting? Can you cache the number of elements shifted? Also, is the original list always sorted? Lastly, is Set a possibility? – Xavier Ho Jun 02 '10 at 21:22
  • What language? Iterate through it or use built in functions like Collection.Contains(obj) – Tim Schmelter Jun 02 '10 at 21:23
  • we can use java. if we iterate through the list, we can just locate the element in O(n). Is there some way we can do better. we dont know how much is shifted in the beginning. Original is sorted. – hao Jun 02 '10 at 21:29
  • 3
    dupe: http://stackoverflow.com/questions/1878769/searching-a-number-in-a-rotated-sorted-array –  Jun 02 '10 at 21:30

3 Answers3

4

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 (/).

finrod
  • 1,398
  • 11
  • 8
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.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • How to find such a shift point in the array using binary search? – Michał Trybus Jun 02 '10 at 21:25
  • @Michał Trybus, it's hard to explain in just a few words. You're searching for the lowest value in the array that's less than array[0], which requires changing the testing condition and the adjustment of the range after each test. – Mark Ransom Jun 02 '10 at 21:38
0

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

Amber
  • 507,862
  • 82
  • 626
  • 550