#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.

class Solution(object):    def search(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: int        """        left=0        right=len(nums)-1        while left <= right:            mid = (left+right)/2            if target == nums[mid]:                return mid            if nums[mid] >= nums[left]:                if target < nums[mid] and target >= nums[left]:                    right=mid-1                else:                    left=mid+1            elif nums[mid] < nums[right]:                if target > nums[mid] and target <= nums[right]:                    left=mid+1                else:                    right=mid-1        return -1