Search in Rotated Sorted Array (Java+Python)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

       

Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

       

Throgh observation we can see, no matter how a sorted array be rotated, there is

 always one side is sorted.

       

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

       

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

       

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my         solution will also cover duplicate exist situation. 

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.