Loading...
Loading...
Loading...
A railway app stores train numbers in increasing order. During an update, the list got rotated: some numbers from the front moved to the back, in the same order. For example, 11 22 33 44 55 may become 44 55 11 22 33. The list may also be left as it was.
All train numbers are different. Print the index of train number t, counting from 0, or -1 if it is not in the list.
-1.Example 1
Input
7 12 45 51 67 3 8 12 30
Output
5
12 is in the part after the rotation point, at index 5.
Example 2
Input
5 50 44 55 11 22 33
Output
-1
50 is not in the list.
Try the problem first. Open one hint at a time.
Split the range at the middle. At least one of the two halves is sorted with no drop inside.
If a[lo] <= a[mid], the left half is sorted. Otherwise the right half is sorted.
For the sorted half, check whether t lies between its two ends. If yes, search there; if not, search the other half.
Use <= in a[lo] <= a[mid]: when only two numbers are left, lo and mid are the same index.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor