Python solution (beat over 99.2%) (Bisect) Time: O(logN) Space: O(1)


  • 0
    J
    def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            #find the rotate point
            if(not nums):
                return -1
            length = len(nums)
            l, r = 0, length - 1
            while(l < r):
                mid = (l + r) / 2
                if(nums[mid] > nums[r]):
                    l = mid + 1
                else:
                    r = mid
            offset = length - l
            l, r = 0, length - 1
            while(l <= r):
                mid = (l + r) / 2
                left = nums[l-offset]
                right = nums[r-offset]
                middle = nums[mid-offset]
                if(middle == target):
                    return mid - offset if mid >= offset else mid - offset + length
                if(target > middle):
                    l = mid + 1
                else:
                    r = mid - 1
            return -1
    

    Since the array just shifts for some elements, we can always pretend to use the original bisect method to search for it with a certain offset for every element's index.
    eg. [4, 5, 1, 2, 3]
    the array is a shift version of [1, 2, 3, 4, 5]
    the minimum element is 1, its index in the shift version is 2, the offset for the original array is 3
    so every time you want to get nums[i] in an original array, just find it in the shift version array as nums[i - offset].
    eg.nums[3] in original array is 4, and nums[3 - 3] in the shift version array is also the one you want.
    the whole method is a linear reflection of the index.
    Also, here I utilize a feature in python : index can be negative!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.