33.md

解法一

40ms, beat: 85%

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        lo, hi = 0, n-1
        while lo < hi:
            mid = (lo + hi)>>1
            if nums[mid] > nums[hi]: lo = mid + 1
            else: hi = mid
        rot = lo
        lo, hi = 0, n -1
        while lo <= hi:
            mid = (lo + hi)>>1
            realmid = int((mid + rot) % n)
            if nums[realmid] == target: return realmid
            if nums[realmid] < target: lo = mid + 1
            else: hi = mid -1
        return -1

解法二

40 - 48ms

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        lo, hi = 0, n-1
        while lo <= hi:
            mid = (lo + hi)>>1
            if nums[mid] == target: return mid
            if nums[mid] < nums[hi]:
                if nums[mid] < target and target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid -1
            else:
                if nums[lo] <= target and target < nums[mid]:
                    hi = mid -1
                else:
                    lo = mid + 1
        return -1