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

• ``````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!

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