def bisect_f(f, lo, hi):
    assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        assert f(lo) and not f(hi)
    assert hi - lo == 1
    assert f(lo) and not f(hi)
    return lo


class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        if len(nums) == 1:
            if nums[0] == target:
                return 0
            return -1

        def getPivot():
            #
            #   *
            #  *
            # *
            #      *
            #     *
            #    *
            # On left side if => nums[0]
            # On right side if <= nums[-1]
            # Find first i where nums[i] on the left and nums[i+1] is on the right
            #
            # Note we can't do this efficiently if duplicates are allowed
            # For example consider the list where you have
            #   [0,0,...,0,0,1,-1,0,0,...,0,0]
            # It's not possible to find the pivot sublinearly because local info around indices are all the same

            if nums[0] < nums[-1]:
                # Not rotated
                return 0
            assert nums[-1] < nums[0]

            def isOnLeft(i):
                return nums[0] <= nums[i]

            def isOnRight(i):
                # This can also be written as nums[i] < nums[0] (not isOnLeft)
                # because nums[-1] and num[0] are adjacent in the sorted list with no repeats
                return nums[i] <= nums[-1]

            lo = 0
            hi = len(nums) - 1

            assert isOnLeft(lo) and isOnRight(hi)
            index = bisect_f(isOnLeft, lo, hi)
            assert isOnLeft(index) and isOnRight(index + 1)

            return index + 1

        pivot = getPivot()
        # print(nums[:pivot], nums[pivot:])

        def remap(index):
            return (index + pivot) % len(nums)

        lo = 0
        hi = len(nums) - 1
        if nums[remap(hi)] == target:
            return remap(hi)
        if target < nums[remap(lo)] or nums[remap(hi)] <= target:
            return -1

        assert nums[remap(lo)] <= target < nums[remap(hi)]
        index = bisect_f(lambda index: nums[remap(index)] <= target, lo, hi)
        assert nums[remap(index)] <= target < nums[remap(index + 1)]

        if nums[remap(index)] == target:
            return remap(index)
        return -1