#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