Given a sorted array of n integers that has been rotated an unknown number of times, write a Java program to find the index of the element in the array. You may assume that the array was originally sorted in increasing order. Try to modify the binary search algorithm.

Example:

Input: Find 5 in {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}

ans: 8 (the index of 5 in the array)

Note

Array1 10, 15, 20, 0, 5

Array2 50, 5, 20, 30, 40

Hint: In classic binary search, we compare x with the midpoint to figure out if x belongs on the left or the right side. The complication here is that the array is rotated. Note that both Arrays 1 and 2 have a midpoint of 20, but 5 appears on the left side of one and on the right side of the other. Therefore, comparing the target with the midpoint is not sufficient.

However, if we look a bit deeper, we can see that one half of the array must be ordered normally (in increasing order). We can therefore look at the normally ordered half to determine whether we should focus on the left or the right half. For example, if we are searching for 5 in Array1, we can look at the left element (10) and the middle element (20). Since 10<20, the left half must be ordered normally. And, since 5 is not between those, we know that we must search the right half.

In Array2, we can see that since 50>20, the right half must be ordered normally. We turn to the middle (20) and right (40) element to check if 5 would fall between them. The value 5 would not; therefore, we search the left half