#!/usr/bin/env python3

__author__ = 'Wei Mu'

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        if nums == []:
            return -1
        if len(nums) == 1:
            return (nums[0] == target)-1
        
        l_ind = 0
        r_ind = len(nums) - 1
        
        start = self.find_start(nums, l_ind, r_ind)
        
        if target < nums[start]:
            return -1
        elif (start == 0 and nums[-1] < target) or (start != 0 and nums[start - 1] < target):
            return -1
        
        if target > nums[-1]:
            l_ind = 0
            r_ind = start - 1
        else:
            l_ind = start
            r_ind = len(nums) - 1
        
        if l_ind == r_ind and nums[l_ind] == target:
            return l_ind
        elif l_ind == r_ind and nums[l_ind] != target:
            return -1
        
        
        
        while r_ind != l_ind:
            # print(l_ind, r_ind)
            if nums[r_ind] == target:
                return r_ind
            elif nums[l_ind] == target:
                return l_ind
            if r_ind - l_ind == 1:
                return -1
            
            mid = (r_ind + l_ind) // 2
            
            if nums[mid] > target:
                r_ind = mid
            else:
                l_ind = mid
        
    def find_start(self, nums, l, r):
        mid = (l+r)//2

        if r - l == 1 and nums[l] > nums[r]:
            return r
        elif r - l == 1 and nums[l] < nums[r]:
            return 0

        elif nums[l] > nums[mid]:
            return self.find_start(nums, l, mid)
        else:
            return self.find_start(nums, mid, r)
